package Graph;

public class TwoColor {

private boolean[] visited;

private boolean[] color;

private boolean isTwoColorable = true;

public TwoColor(Graph g){

visited = new boolean[g.V()];

color = new boolean[g.V()];

for (int i = 0; i < g.V(); i++) {

if (!visited[i]) {

dfs(g, i);

}

}

}

public void dfs(Graph g, int v) {

visited[v] = true;

for (int w : g.adj(v)) {

if (!visited[w]) {

color[w] = !color[v];

dfs(g, w);

}

else if (color[w] == color[v]) isTwoColorable = false;

}

}

public boolean isBipartite() {

return isTwoColorable;

}

}