Connected Components — DFS/BFS Marking

Algorithm

int connectedComponents(List[] graph) {
  boolean[] visited = new boolean[graph.length];
  int count = 0;
  for (int i = 0; i < graph.length; i++) {
    if (!visited[i]) {
      dfs(i, graph, visited);
      count++;
    }
  }
  return count;
}

Component sizes / representatives

Modify traversal to collect vertices. Store in list per component.

Union-Find alternative

Process each edge once via union. Number of components = V - number of successful unions. O((V+E)·α(V)).

Applications

Number of islands. Detecting clusters. Preprocessing before per-component algorithms.