Union-Find: Who Is in Which Group?

Merging groups

People become friends pair by pair; you keep asking “same friend group?”. Union-find answers in almost O(1).

• Each element points to a parent; following parents reaches the group's leader.
• find(x) – follow parents to the leader (and shorten the path on the way).
• unite(a, b) – if the leaders differ, attach the smaller group under the bigger one.

Think of it like this: Every club has a president. Two people are in the same club if they have the same president. When clubs merge, one president reports to the other.

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

struct DSU {
    vector<int> parent, size;
    DSU(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];    // path compression
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;             // already together
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;                        // smaller group joins the bigger one
        size[a] += size[b];
        return true;
    }
};

int main() {
    DSU d(6);
    d.unite(0, 1);
    d.unite(2, 3);
    d.unite(1, 3);
    cout << (d.find(0) == d.find(2)) << " " << (d.find(0) == d.find(4)) << endl;
    cout << "size of 0's group: " << d.size[d.find(0)] << endl;
    return 0;
}

Output

1 0
size of 0's group: 4

Remember: If unite(a, b) returns false, a and b were already connected – the new edge closes a loop.