DSU (Union-Find)

Concept

DSU (Disjoint Set Union) efficiently manages a collection of disjoint sets. It supports two operations: Find (which set does an element belong to?) and Union (merge two sets). Path compression makes Find nearly O(1) amortized.

When to Use

  • ▸Kruskal's MST — checking if adding an edge creates a cycle
  • ▸Counting connected components dynamically as edges are added
  • ▸Checking if two elements are in the same group
  • ▸Problems involving merging groups (friend circles, network connectivity)

Intuition

Each set is a tree where every node points to its parent. The root represents the set. To check if two elements are in the same set, follow parents to the root — same root means same set. Path compression flattens the tree during Find, so future queries are instant. Union by size keeps trees balanced by attaching the smaller tree under the larger one.

Complexity

Time
O(alpha(n)) per operation (nearly O(1))
Space
O(n)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

// --- Basic DSU (Path Compression) ---

int findRoot(int n, vector<int> &parent){
    if(n == parent[n]) return n;
    return parent[n] = findRoot(parent[n], parent);
}

// Init:
// vector<int> parent(n);
// for(int i = 0; i < n; i++) parent[i] = i;
//
// Union:
// int A = findRoot(a, parent);
// int B = findRoot(b, parent);
// if(A != B) parent[A] = B;


// --- DSU with Union by Size ---

vector<int> pa, sz;

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

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);
    pa[b] = a;
    sz[a] += sz[b];
    return true;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    pa.assign(n, 0);
    sz.assign(n, 1);
    for(int i = 0; i < n; i++) pa[i] = i;

    int components = n;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        if(unite(a, b)) components--;
    }

    cout << components << "\n";

    return 0;
}

// Sample Input:
// 5 3
// 0 1
// 2 3
// 1 3
//
// Sample Output:
// 2