Connected components

To split an undirected graph or a grid into connected components, start a search from every vertex that no earlier search has reached. This counts the components, measures their sizes and tells whether two vertices are in the same one, all in O(n + m). If the edges are added one by one between the questions, use a disjoint set union instead.

Explanation

Five people live in a small town, and some of them are friends: 1 and 2, 2 and 3, 4 and 5. Tell person 1 a rumour and watch where it goes. Two people had to be told, because the town has two groups of friends.

Fig. 1. 5 people, friendships 1–2, 2–3, 4–5.

In a bigger crowd the groups are harder to see. Here are 9 people and 7 friendships. How many people must you tell so that all 9 hear the rumour?

Fig. 2. 9 people, 7 friendships.

One rumour told to person 1 finds everyone who will hear it from person 1, the way breadth-first search finds everything reachable from its start. The obvious plan is to tell each of the 9 people a rumour in turn and see which different groups come out. Persons 1, 4, 7 and 8 each find the same group of four. Persons 2, 3 and 6 each find the same group of three, and persons 5 and 9 each find the same pair. That is 9 rumours and 29 people reached for only 3 groups, and the groups still have to be compared to see which are the same.

Every rumour after the first one in a group is wasted, and you can tell in advance which ones. A rumour reaches everyone in its group, so a person who has already heard is in a group that has been found. So go through the people in order, from 1 to 9. If a person has already heard a rumour, skip them. If not, tell them a new rumour, let it spread from friend to friend, and write its number next to everyone it reaches. When the last person has been checked, the number of rumours started is the answer.

A group of people who can all reach each other through friends is a connected component, and each rumour finds exactly one.

Nobody has heard a rumour yet, so nobody has a number.

Person 1 has not heard a rumour yet, so they are told rumour 1 and get the number 1.

Person 4 hears rumour 1 from person 1 and gets the number 1.

Person 7 hears rumour 1 from person 4 and gets the number 1.

Person 8 hears rumour 1 from person 7 and gets the number 1.

Person 2 has not heard a rumour yet, so they are told rumour 2 and get the number 2.

Person 3 hears rumour 2 from person 2 and gets the number 2.

Person 6 hears rumour 2 from person 2 and gets the number 2.

Person 3 has already heard rumour 2, so the scan skips them.

Person 4 has already heard rumour 1, so the scan skips them.

Person 5 has not heard a rumour yet, so they are told rumour 3 and get the number 3.

Person 9 hears rumour 3 from person 5 and gets the number 3.

Person 6 has already heard rumour 2, so the scan skips them.

Person 7 has already heard rumour 1, so the scan skips them.

Person 8 has already heard rumour 1, so the scan skips them.

Person 9 has already heard rumour 3, so the scan skips them.

The scan has checked all 9 people. 3 rumours were started, so there are 3 groups.

1/17

Fig. 3. The scan of the 9 people. The arrow $s$ points at the person the scan checks, and the row of boxes holds the number of each person.

Three people must be told: persons 1, 2 and 5. Every person also got the number of their group: persons 1, 4, 7 and 8 got 1, persons 2, 3 and 6 got 2, and persons 5 and 9 got 3. So the groups have 4, 3 and 2 people. Two people hear each other's rumours exactly when their numbers are equal. Persons 4 and 8 do, since both have 1. Persons 3 and 8 don't, since they have 2 and 1.

Islands

On a map of land and water, each island is a group, and two land squares that share a side are friends. The same loop goes through the squares row by row and starts a new search at every land square that has no number yet.

Fig. 4. The scan of the whole map.

Implementation

In code, people are vertices and friendships are edges. A vertex is reached once it has a number.

Let's keep the numbers in an array comp: comp[v] is the number of the component of v, and comp[v] == 0 while v is not reached. This one array is both the mark of the search and the answer. The variable count is the number of searches started so far.

1. Initialise: comp[v] = 0 for every vertex v, and count = 0.

2. Start a new component: go through s = 1, 2, …, n. If comp[s] == 0, increase count, set comp[s] = count and push s to an empty queue.

3. Take the next vertex v from the front of the queue.

4. Expand its edges: look at each neighbour u of v.

5. Reach it: if comp[u] == 0, set comp[u] = count and push u.

6. Stop: the search stops when the queue is empty, and the loop goes on to the next s. The loop stops after vertex n.

The program reads n and m, then m lines u v: a two-way edge between u and v. Vertices are numbered from 1 to n. The program prints the number of components, then comp[v] for every vertex, then the size of every component. For the crowd of 9 the input is:

9 7
1 4
4 7
7 8
2 3
2 6
3 6
5 9

The graph is stored as an adjacency list, where adj[v] lists the neighbours of v. Each edge goes into both lists. The search inside the loop is the BFS you know.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // initialise
    vector<int> comp(n + 1, 0);
    int count = 0;
    vector<int> size(n + 1, 0);   // only needed for the sizes

    for (int s = 1; s <= n; s++) {
        if (comp[s] != 0) continue;   // already reached: skip

        // start a new component
        count++;
        comp[s] = count;
        size[count]++;   // only needed for the sizes
        queue<int> q;
        q.push(s);

        while (!q.empty()) {          // stop: when the queue is empty
            // take the next vertex
            int v = q.front();
            q.pop();

            // expand its edges
            for (int u : adj[v]) {
                if (comp[u] == 0) {
                    // reach it
                    comp[u] = count;
                    size[count]++;   // only needed for the sizes
                    q.push(u);
                }
            }
        }
    }

    cout << count << '\n';
    for (int v = 1; v <= n; v++) {
        cout << comp[v] << (v < n ? ' ' : '\n');
    }

    // print the size of every component; remove this block if you only need the numbers
    for (int k = 1; k <= count; k++) {
        cout << size[k] << (k < count ? ' ' : '\n');
    }
}

A recursive DFS, shorter to write, can replace the BFS inside the loop. Only the search changes: every vertex gets the same number, though the order inside a component may differ.

Over all searches together, each vertex gets a number once and is taken from the queue once, each edge is checked twice, once from each end, and the loop itself checks n vertices. So the program takes O(n + m) time and O(n + m) memory, however many searches there are.

Sizes

The program counts the size of each component while numbering: it adds 1 to size[count] every time a vertex gets the number count, in the lines marked "only needed for the sizes". There are at most n components, so size has n + 1 cells. On the crowd of 9 the last line of the output is 4 3 2.

To list the members of each component, keep vector<vector<int>> members(n + 1) instead and push each vertex into members[count] when it gets its number.

Checking two vertices

After the loop, "are u and v in the same component?" is the check comp[u] == comp[v], one comparison per question.

Grids

On the island map, # is land and . is water. A vertex is a land square (r, c), and its neighbours are the land squares that share a side with it. The grid has R rows and C columns, and g holds its rows as strings. Only these lines change: comp is two-dimensional, the loop goes over all squares, and the search checks the four side neighbours.

int dr[] = {-1, 1, 0, 0};   // up, down, left, right
int dc[] = {0, 0, -1, 1};

// initialise
vector<vector<int>> comp(R, vector<int>(C, 0));
int count = 0;

for (int sr = 0; sr < R; sr++) {
    for (int sc = 0; sc < C; sc++) {
        if (g[sr][sc] != '#' || comp[sr][sc] != 0) continue;  // water or reached

        // start a new component
        count++;
        comp[sr][sc] = count;
        queue<pair<int, int>> q;
        q.push({sr, sc});

        while (!q.empty()) {
            // take the next vertex
            auto [r, c] = q.front();
            q.pop();

            // expand its edges
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;  // outside the grid
                if (g[nr][nc] != '#') continue;                        // water
                if (comp[nr][nc] == 0) {
                    // reach it
                    comp[nr][nc] = count;
                    q.push({nr, nc});
                }
            }
        }
    }
}

On the island map this finds 4 islands of 3, 5, 3 and 3 squares. The time and the memory are O(R \cdot C). A 1000 \times 1000 map has 10^6 squares, so BFS makes at most about 4 \cdot 10^6 neighbour checks. A recursive search on such a map can run out of memory for calls, as the DFS article explains.

Correctness proof

When the search with number $k$ ends, the vertices with number $k$ are exactly the vertices that can be reached from its start. This is what BFS does, as the BFS article shows. A search never changes a number given by an earlier search, because it reaches only vertices with comp_u = 0.

Same number means same component. Two vertices with number $k$ can both be reached from the start of search $k$, so they can reach each other through it.

Same component means same number. Take two vertices $u$ and $v$ in one component, and say $u$ got its number first, from search $k$. Search $k$ reaches everything that can be reached from its start, and $v$ can be reached from $u$, so $v$ gets the number $k$ too.

The count is right. A new search starts only at a vertex with no number, and by the argument above that vertex is in no component found so far. So each search finds a new component. The loop checks every vertex, so every vertex ends up with a number, and no component is missed.

Common mistakes

• Starting a search from every vertex, or clearing comp before each search, so no vertex is ever skipped and the count comes out as n. Skip a vertex that already has a number, and fill comp with zeros only once, before the loop.

• Counting components as n - m, which is right only when no component has a cycle: an edge on a cycle joins two vertices already in one component. Count the searches instead.

• Storing a two-way edge in one list only, with adj[v].push_back(u); left out, so the search follows an edge only from its first vertex and splits a component in several. Add every edge to both lists.

• Starting a new search for every "same component?" question, which can walk a whole component each time. Number the vertices once, before the questions, and compare comp[u] and comp[v].

• Not clearing adj and comp when the input has several test cases, so old edges and old numbers carry over into the next test. Call adj.assign(n + 1, {}) and comp.assign(n + 1, 0) at the start of every test.

Similar algorithms

Disjoint set union is for edges that arrive one by one, with questions between them, such as "after each new road, how many components are there?". Running the loop again after every edge costs O(n + m) each time. A disjoint set union merges the two components of each new edge in almost constant time, without searching again.

Strongly connected components are for one-way edges. There, "can reach" doesn't work both ways, and the count from this loop depends on the order of the vertices. With the single edge 2 \to 1 it counts 2 components, and with 1 \to 2 it counts 1. Components where everyone can reach everyone along the arrows need a different algorithm.

Practice