Disjoint Set Union (DSU)

Disjoint Set Union maintains a partition into nonoverlapping groups. It supports finding which group contains a vertex and merging two whole groups. Also called Union-Find, it is ideal when edges are only added and we repeatedly ask whether two vertices are connected. Path compression and union by size make a long sequence of operations almost linear. DSU does not store graph paths and does not generally support deleting edges. Our implementation processes online edge additions, connectivity queries, and component-size questions.

Prerequisites: Arrays and Vectors, Trees terminology, and connected components.

Build the idea

1. 1. Represent each group by a rooted parent forest. Start with n separate vertices. Set parent[v]=v and size[v]=1. A vertex whose parent is itself is a representative, or root, for its component. Following parent links eventually reaches that root. These parent links are bookkeeping choices, not necessarily actual graph edges and not the rooting of the graph being modeled. Two vertices are connected precisely when their representatives are equal. Initially the component counter is n, including isolated vertices.
2. 2. Find the representative. A plain find follows parent links. If all unions attach new roots badly, a chain can become linear in n. Path compression changes the parents on the traversed path to point directly to the representative. For 7→4→2→2, find(7) returns 2 and rewrites both 7 and 4 to point to 2. Membership does not change because every rewritten node already belonged to the same group. This lesson uses iterative compression so even an unexpectedly deep parent chain does not require recursive call-stack space.
3. 3. Merge roots, not arbitrary vertices. To join a and b, first find their roots ra and rb. If equal, nothing changes: the new edge is redundant for connectivity. Otherwise attach the smaller component root below the larger one, add their sizes at the surviving root, and decrease the component count by one. Sizes stored at non-roots may be stale; always query size[find(v)]. The root ID has no intrinsic graph meaning and may change after a union. Do not assume vertex 1 is always the representative of its component.
4. 4. Work a small sequence. With vertices 1..5, add 1–2: the groups become {1,2},{3},{4},{5}. Add 2–3: find(2) identifies the first group's root, so {1,2,3} forms and its size is 3. A query 1,3 returns YES. Adding 1–3 changes no groups because both ends are already connected. Vertex 4 still has size 1. Adding 4–5 leaves two components. Each successful union, and only a successful union, reduces the component counter.
5. 5. Understand the complexity honestly. Union by size alone makes a node's depth O(log n): whenever its depth increases, its component at least doubles. Path compression improves a sequence further. Together the heuristics give amortized O(α(n)) per operation, where α is the inverse Ackermann function and grows extraordinarily slowly. This is a bound across operations, not a proof that every individual call is worst-case constant. Initializing n singleton components still costs O(n). The parent and size vectors occupy linear storage.
6. 6. Connect to graph algorithms. In Kruskal's minimum spanning tree algorithm, sort edges by weight and accept an edge only if unite succeeds. It connects two formerly separate components without creating a cycle. DSU detects whether adding an undirected edge would make a cycle because a preexisting path exists exactly when the endpoints already share a component. It cannot reconstruct that path from its parent forest. Ordinary DSU also cannot split a component after deletion; offline reverse processing or rollback DSU is a different technique with additional restrictions and bookkeeping.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<numeric>
#include<utility>
using namespace std;
struct DSU{
    vector<int>parent,size;
    int components;
    explicit DSU(int n):parent(n+1),size(n+1,1),components(n){
        // Each vertex initially represents its own singleton component.
        iota(parent.begin(),parent.end(),0);
    }
    int find(int v){
        int root=v;
        while(parent[root]!=root){
            root=parent[root];
        }
        while(parent[v]!=v){ // Compress the old path iteratively.
            int next=parent[v];
            parent[v]=root;
            v=next;
        }
        return root;
    }
    bool unite(int a,int b){
        // Only representative roots may be linked or have their sizes combined.
        a=find(a);
        b=find(b);
        if(a==b){
            return false; // A redundant edge does not reduce components.
        }
        if(size[a]<size[b]){
            swap(a,b);
        }
        parent[b]=a; // Attach the smaller component root.
        size[a]+=size[b];
        --components;
        return true;
    }
    int componentSize(int v){
        return size[find(v)];
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    if(!(cin>>n>>q)||n<1||q<0){
        return 0;
    }
    DSU dsu(n);
    while(q--){
        char op;
        int u,v;
        cin>>op>>u;
        if(u<1||u>n){
            return 0;
        }
        if(op=='S'){
            cout<<dsu.componentSize(u)<<'\n';
        }
        else{
            cin>>v;
            if(v<1||v>n){
                return 0;
            }
            if(op=='+'){
                dsu.unite(u,v);
                cout<<dsu.components<<'\n';
            }
            else if(op=='?'){
                cout<<(dsu.find(u)==dsu.find(v)?"YES":"NO")<<'\n';
            }
        }
    }
}

Complexity analysis

Initialization is O(n). With both union by size and path compression, q operations take O(q α(n)) amortized time after initialization; total O(n+q α(n)), with O(n) storage. A size query performs find and has the same amortized bound. With only union by size, O(log n) worst-case find is available. Avoid describing DSU as literally O(1) for every call.

Example input and output

Read n q with n ≥ 1 and q ≥ 0. + u v adds an undirected edge and prints the number of components; ? u v prints connectivity; S u prints its component size. IDs are 1..n. Repeated edges and self-loops are allowed and do not merge an already connected component.

Input

5 8
+ 1 2
+ 2 3
? 1 3
S 2
+ 1 3
? 1 5
+ 4 5
S 5

Output

4
3
YES
3
3
NO
2
2

The first two additions create a size-three component. Adding 1–3 is redundant and leaves three components. Joining 4 and 5 leaves two components, and vertex 5 belongs to a component of size two.

Practical applications

Use DSU for incremental connectivity, Kruskal, cycle prevention during graph/tree editing, merging accounts or equivalence classes, and offline connectivity problems. For a fixed graph with no updates, one DFS/BFS component pass may be simpler. Weighted or parity DSU maintains extra relations and needs additional formulas beyond this implementation.

Check your understanding

When adding an edge u–v does DSU detect a cycle?

Put it into practice

Read edges in order and print the index of the first edge whose endpoints are already connected, or 0 if none exists.