Connected Components
Partition an undirected graph into maximal connected groups. A flood fill (BFS/DFS) from each unvisited node labels everything it can reach with the same component id.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
for each unvisited node new component id flood-fill all reachable nodes count = number of components
Reference implementation
for n in V:
if n not in comp:
cid += 1
flood_fill(n, cid) # BFS/DFS