PLEASE HELP FINISH THE CODE

Graph Class

import java.io.PrintWriter; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList;

public class Graph { private static class Vertex { LinkedList adj; // adjacency list int color; // color assigned to vertex int parent; // parent in bfs forest/tree boolean visited; // already visited or not ? // ADD/MODIFY AS YOU SEE FIT

// constructor Vertex() { adj = new LinkedList(); parent = -1; visited = false; // ADD/MODIFY AS YOU SEE FIT }

// add neighbor w void addNeighbor(int w) { adj.addLast(w); } }

// Vertices are labeled 1 through n; hence any array allocated // has n+1 components with component [0] not used public Graph(int n) { nVertices = n; vertices = new Vertex[n + 1]; // only [1] through [n] will be used // construct the vertices for (int v = 1; v <= nVertices; v++) vertices[v] = new Vertex();

}

private int nVertices; // number of vertices; vertices are 1 .. nVertices private Vertex[] vertices; // array of vertices; [0] not used // ADD/MODIFY AS YOU SEE FIT

// add the edge v-w public void addEdge(int v, int w) { vertices[v].addNeighbor(w); vertices[w].addNeighbor(v); } // end of addEdge

// print the adjacency lists of vertices to the given // printwriter public void printAdjacencies(PrintWriter output) { int v; int x; output.println("Adjacency lists of graph:"); // COMPLETE THE CODE for (v = 1; v <= nVertices; v++) { output.printf("%2d:", v); output.print(vertices[v].adj); output.printf(" "); }

} // end of printAdjacencies

// print parent of each vertex in BFS tree to given printwriter public void printParents(PrintWriter output) { int v; output.println("Parents in BFS tree:"); output.printf("Vertex: "); for (v = 1; v <= nVertices; v++) output.printf("%2d ", v); output.println(); output.printf("Parent: "); for (v = 1; v <= nVertices; v++) output.printf("%2d ", vertices[v].parent); output.println(); } // end of printParents

// Pre: graph is connected, has at least one edge, and list is valid // Return value: true if graph is bipartite and false otherwise // Post: previous value of list is lost // graph remains unchanged // if graph is bipartite, list has vertices of color 1, followed // by 0, followed by vertices of color 2 // otherwise, list has vertices of an odd cycle in cyclic order // Uses: BFS // Complexity: O(m+n) public boolean bipartite () { // COMPLETE THE CODE

} // end of bipartite } // end of class Graph

main class

import java.io.File; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner;

public class Main {

public static void main(String[] args) throws FileNotFoundException { File f = new File("input.txt"); Scanner sc = new Scanner(f); PrintWriter output = new PrintWriter("output.txt"); int n = sc.nextInt(); // number of vertices int m = sc.nextInt(); // number of edges Graph g = new Graph(n); int i = 1; while(i <= n) { int v = sc.nextInt(); int w = sc.nextInt(); i++; g.addEdge(v, w); }

g.printAdjacencies(output); g.printParents(output); System.out.print(g.bipartite()); System.out.println(" ");

int n2 = sc.nextInt(); // number of vertices int m2 = sc.nextInt(); // number of edges Graph g2 = new Graph(n2);

while(sc.hasNextLine()) { int v2 = sc.nextInt(); int w2 = sc.nextInt(); i++; g2.addEdge(v2, w2); } output.print(" "); g2.printAdjacencies(output); g2.printParents(output); System.out.print(g2.bipartite()); output.close(); }

}

input

7 7 1 3 2 3 2 5 2 7 4 5 4 6 4 7

7 8 1 3 1 4 2 3 2 5 2 7 4 5 4 6 4 7