Connected Components
Partition a graph into groups of mutually reachable vertices.
| Algorithm | Complexity | When to use |
|---|---|---|
O(V + E) |
Undirected graphs. Labels each vertex with its component number. |
|
O(V + E) |
Directed graphs. Vertices u and v are in the same component iff there is a path from u to v and from v to u. |
|
O(V + E) |
Undirected graphs. Finds 2-connected subgraphs and articulation points (vertices whose removal disconnects the graph). |
|
Near O(1) per edge |
Online: edges are added one at a time and component queries are answered between insertions. Uses disjoint sets. |
For a static undirected graph, use connected_components. For directed
graphs, use strong_components. If edges arrive incrementally and you need
live connectivity queries, use incremental_components.
|