Disjoint Set Union¶

In one sentence

Keep people in groups as little trees: every person points to a parent, the top of the tree (the root) names the group, and "merge two groups" is just "point one root at the other".

1. What problem does it solve?¶

Example — 1167C · News Distribution (rating 1400)

A social network has \(n\) users and \(m\) groups; each group lists its members. If a user learns some news, they tell everyone in every group they belong to, those people tell their groups, and so on. For each user \(x\), print how many users will eventually know the news if \(x\) is the first to learn it.

Limits: \(n, m \le 5\cdot10^5\), total size of all groups \(\le 5\cdot10^5\).

Input          Output
7 5
3 2 5 4
0
2 1 2
1 1
2 6 7          4 4 1 4 4 2 2

Users who share a group end up in the same "news bubble", and bubbles merge whenever two of them share a member. The question per user is simply "how big is my bubble?"

The naive way. Store a bubble number id[x] for each user. Merging two bubbles means relabelling every member of one of them, which can cost \(O(n)\) per merge and \(O(n^2)\) in total.

DSU merges in (almost) constant time by relabelling only one entry: the root.

2. How it works¶

2.1 Groups as trees¶

p[x] is the parent of \(x\). A root points to itself: p[r] == r. Two users are in the same group exactly when they have the same root.

start:        p = [1, 2, 3, 4, 5]          every user is their own group
union(2, 5):  p[2] = 5                     2 → 5
union(2, 4):  find(2) = 5, p[5] = 4        2 → 5 → 4

2.2 `find` with path compression¶

find(x) walks up parents until it reaches the root. Path compression (return p[x] = find(p[x]);) then points every node on that walk directly at the root, so the next find on any of them takes one step.

before find(2):   2 → 5 → 4          after:   2 → 4,  5 → 4

With path compression, a long sequence of operations costs close to \(O(1)\) each on average (the exact bound is \(O(\log n)\) amortised for compression alone, which is already more than fast enough here).

2.3 Keeping group sizes¶

Store sz[r] = size of the group whose root is \(r\). When root fa is attached under root fb, do sz[fb] += sz[fa]. The answer for user \(x\) is sz[find(x)].

2.4 Trace on the example¶

Each group is merged as "first member ∪ every other member".

group	unions	groups after
`2 5 4`	(2,5), (2,4)	{2,5,4}, {1}, {3}, {6}, {7}
(empty)	—	same
`1 2`	(1,2)	{1,2,4,5}, {3}, {6}, {7}
`1`	—	same
`6 7`	(6,7)	{1,2,4,5}, {3}, {6,7}

Sizes per user: \(4, 4, 1, 4, 4, 2, 2\).

Cost. Each group of size \(k\) does \(k - 1\) unions, so at most \(5\cdot10^5\) unions in total, each nearly \(O(1)\).

3. Lesson notes (23 August)¶

Two fixes before this template compiles

union is a reserved word in C++ (it declares a union type), so the function must be renamed, e.g. to unite. And p must be visible inside find / union, so declare it outside main (or capture it in lambdas). The note is kept unchanged below; the worked solution in §4 applies both fixes.

1. init¶

int n;

vector<int> p(n + 1);
for(int i = 1; i <= n; i++) {
    p[i] = i;
}

2. root find¶

int find(int x) {
    if(x == p[x]) {
        return x;
    }
    return find(p[x]);
}

int find(int x) {
    if(x == p[x]) {
        return x;
    }
    return p[x] = find(p[x]);
}

3. set union¶

void union(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    if(fa == fb) {
        return;
    }
    p[fa] = fb;
}

4. Worked solution — News Distribution¶

The 23 August template with union renamed to unite, p made global, and sizes added.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

vector<int> p, sz;

int find(int x) {
    if(x == p[x]) {
        return x;
    }
    return p[x] = find(p[x]);
}

void unite(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    if(fa == fb) {
        return;
    }
    p[fa] = fb;
    sz[fb] += sz[fa];
}

void solve() {
    int n, m;
    cin >> n >> m;

    p.resize(n + 1);
    sz.assign(n + 1, 1);
    for(int i = 1; i <= n; i++) {
        p[i] = i;
    }

    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        int first = 0;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            if (j == 0) {
                first = x;
            } else {
                unite(first, x);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << sz[find(i)] << " ";
    }
    cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. When to think "DSU"¶

The statement says…	DSU operation
"\(a\) and \(b\) become friends / are connected / join"	`unite(a, b)`
"are \(a\) and \(b\) in the same group?"	`find(a) == find(b)`
"how many groups are there?"	count \(x\) with `find(x) == x`
"how big is \(x\)'s group?"	`sz[find(x)]`
"split a group"	not DSU: it can only merge

6. Common mistakes¶

Forgetting to initialise p[i] = i

With p full of zeros, every find walks to vertex 0. Initialise before the first union.

Attaching a instead of its root

p[a] = b loses the rest of \(a\)'s tree. Always attach roots: p[find(a)] = find(b).

Updating sz on the wrong root

After p[fa] = fb, only sz[fb] is meaningful. Read sizes through sz[find(x)].

Comparing p[a] == p[b]

Parents are not roots. Two nodes can have different parents and the same root.

7. Practice¶

Problem	Where	Idea
1167C · News Distribution	Codeforces, rating 1400	component sizes (this page)
AIO 2018 · Detective	AIO 2018 Q5	"same / different" statements; we solved it with colouring, a DSU with parity also works
217A · Ice Skating	8-Graph · C, rating 1200	count groups, answer = groups − 1

Credits & licenses

§3 is the DSU note from 23 August, unchanged apart from heading levels. §4 reuses its code with the two fixes described in the warning.
Example, tree pictures, trace, worked solution and mistakes are ours.