Disjoint set union

DSU maintains groups under merging. It answers whether two vertices already belong to the same component.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Initially every vertex is its own representative.
2. Find follows parent links to a representative and compresses the path.
3. Union attaches the smaller set to the larger one.
4. This combination makes a sequence of operations almost linear.
5. p[v] stores a representative link and sz stores root sizes. Path compression shortens future searches; union by size limits tree height.

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

// Key idea: p[v] stores a representative link and sz stores root sizes. Path compression shortens
// future searches; union by size limits tree height.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
struct DSU{
    vector<int>p,sz;
    DSU(int n):p(n+1),sz(n+1,1){
        iota(p.begin(),p.end(),0);
    }
    int find(int v){
        return p[v]==v?v:p[v]=find(p[v]);
    }
    bool unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return false;
        }
        if(sz[a]<sz[b]){
            swap(a,b);
        }
        p[b]=a;
        sz[a]+=sz[b];
        return true;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    DSU sets(n);
    int components=n;
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        if(sets.unite(a,b)){
            components--;
        }
        cout<<components<<'\n';
    }
}

Complexity analysis

O(α(V)) amortized per operation, O(V) space.

Example input and output

Read n q (n≥1), then q vertex pairs a b to merge. Print the number of connected groups after each merge. Repeated merges leave the count unchanged.

Input

5 4
1 2
2 3
4 5
1 3

Output

4
3
2
2

The first three merges reduce five components to two. The last pair is already connected.

Practical applications

Use DSU for incremental connectivity and Kruskal. It does not directly support arbitrary deletions.

Check your understanding

Why use union by size?

Put it into practice

Process new roads and report the number of connected components after each road.