package Graph;

public class ConnectedComponents {

private boolean[] visited;

private int[] id;

private int count;

public ConnectedComponents(Graph g) {

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

id = new int[g.V()];

count = 0;

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

if (!visited[i]) {

dfs(g, i);

count++;

}

}

}

public void dfs(Graph g, int start) {

visited[start] = true;

id[start] = count;

for (int neighbor : g.adj(start)) {

if (!visited[neighbor]) {

dfs(g, neighbor);

}

}

}

public boolean connected(int v, int w) {

return id[v] == id[w];

}

public int id(int v) {

return id[v];

}

public int numberOfConnectedComponents() {

return count;

}

}