Union-Find (Disjoint Set Union)

Key Signals & Indicators

• Dynamic connectivity checks (are A and B connected?)
• Detecting cycles in undirected graphs
• Kruskal's MST, clustering, or grouping relations

// C++ Union-Find (DSU) Template
#include <vector>
#include <numeric>

class DSU {
    std::vector<int> parent, rank;
public:
    DSU(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
        rank.resize(n, 1);
    }
    
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // Path compression
    }
    
    bool unite(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
            parent[rootJ] = rootI;
            if (rank[rootI] == rank[rootJ]) rank[rootI]++;
            return true;
        }
        return false; // Already in same component
    }
};