whoashish's cp notes

Connected Components

3 min read

A connected component is a maximal set of vertices that can all reach each other. Finding them is the “hello world” of graph algorithms and the first thing to check when a problem smells graph-shaped.

By DFS or BFS — 

vector<int> comp;      // comp[v] = component id, -1 if unassigned
int numComponents = 0;
 
void dfsComp(int u, int id) {
    comp[u] = id;
    for (int v : adj[u])
        if (comp[v] == -1) dfsComp(v, id);
}
 
void findComponents(int n) {
    comp.assign(n, -1);
    numComponents = 0;
    for (int i = 0; i < n; i++)
        if (comp[i] == -1) dfsComp(i, numComponents++);
}

By DSU —

Preferable when edges arrive online, when you also need component sizes, or when the graph is given only as an edge list.

DSU dsu(n);
for (auto [u, v] : edges) dsu.unite(u, v);
// components = number of distinct dsu.find(i)
// size of v's component = dsu.size[dsu.find(v)]

See Disjoint Set Union.

Which to use

SituationUse
Static graph, adjacency list readyDFS/BFS
Edges arrive one at a timeDSU
Edges are also removeddynamic connectivity
Directed graphSCC — plain components are the wrong notion
Need bridge-resilience2-edge-connected components
Need cut-vertex-resiliencebiconnected components

Directed graphs

Running undirected component finding on a directed graph gives weakly connected components (connectivity ignoring direction). If the problem cares about reachability in the direction of the edges, you want strongly connected components instead. Confusing the two is a classic wrong-answer.

Things components immediately give you

  • Is the graph connected? One component.
  • Minimum edges to connect the graph: .
  • Number of spanning forests / can a spanning tree exist: a spanning tree exists iff there is one component.
  • Bipartiteness is checked per component — see Bipartite Graphs.
  • Component sizes answer “how many pairs of vertices are connected”: .
  • Grid flood fill — islands, regions, paint bucket; the same algorithm with an implicit graph.

Flood fill on a grid

int islands(vector<string>& g) {
    int R = g.size(), C = g[0].size(), cnt = 0;
    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,1,-1};
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (g[i][j] != '1') continue;
            cnt++;
            queue<pair<int,int>> q; q.push({i, j}); g[i][j] = '0';
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                for (int d = 0; d < 4; d++) {
                    int rr = r + dr[d], cc = c + dc[d];
                    if (rr < 0 || cc < 0 || rr >= R || cc >= C) continue;
                    if (g[rr][cc] != '1') continue;
                    g[rr][cc] = '0';
                    q.push({rr, cc});
                }
            }
        }
    return cnt;
}

Marking the cell as visited when pushing (here by overwriting it) rather than when popping keeps the queue .

See also: DFS · BFS · DSU

Graph View