Union-Find (DSU) Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Union-Find (Disjoint Set Union) with path compression + union by size.
struct DSU {
    vector<int> parent, sz;
    int groups;
    DSU(int n) : parent(n), sz(n, 1), groups(n) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);             // hang the smaller tree under the bigger one
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
};

// Undirected cycle / redundant edge: an edge whose two ends already share a root closes a cycle.
// Uses the DSU from the Union-Find template.
vector<int> firstRedundantEdge(int n, const vector<vector<int>>& edges) {   // nodes 1..n
    DSU dsu(n + 1);
    for (auto& e : edges)
        if (!dsu.unite(e[0], e[1])) return e;     // already connected: this edge makes a cycle
    return {};
}

// How many cables to move so all n computers connect (Network Connected):
// spare edges = edges that closed a cycle; you need (groups - 1) of them.
int makeConnected(int n, const vector<vector<int>>& connections) {
    if ((int)connections.size() < n - 1) return -1;
    DSU dsu(n);
    for (auto& c : connections) dsu.unite(c[0], c[1]);
    return dsu.groups - 1;
}

// Grouping by "is equivalent to": union every given pair, then collect each root's members.
// Uses the DSU from the Union-Find template. Here: Smallest String With Swaps.
string smallestStringWithSwaps(string s, const vector<vector<int>>& pairs) {
    int n = s.size();
    DSU dsu(n);
    for (auto& p : pairs) dsu.unite(p[0], p[1]);  // swaps chain: (0,3) and (3,1) let 0, 1, 3 trade freely
    unordered_map<int, vector<int>> members;       // root → indices in that group, increasing
    for (int i = 0; i < n; i++) members[dsu.find(i)].push_back(i);
    for (auto& [root, idx] : members) {
        string chars;
        for (int i : idx) chars += s[i];
        sort(chars.begin(), chars.end());          // inside a group any arrangement is reachable
        for (int k = 0; k < (int)idx.size(); k++) s[idx[k]] = chars[k];
    }
    return s;
}

// Kruskal's minimum spanning tree: cheapest edges first, skip any edge inside one group.
// Uses the DSU from the Union-Find template. Returns -1 if the graph is not connected.
long long kruskal(int n, vector<array<int, 3>> edges) {   // {weight, u, v}, nodes 0..n-1
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total = 0;
    int used = 0;
    for (auto& [w, u, v] : edges) {
        if (!dsu.unite(u, v)) continue;            // would close a cycle: never needed
        total += w;
        if (++used == n - 1) break;                // a spanning tree has exactly n - 1 edges
    }
    return used == n - 1 ? total : -1;
}