并查集与最小生成树：连通分量的演化模型

连通性维护的核心痛点

在图结构中，频繁查询“点 $u$ 与点 $v$ 是否连通”，并在两个连通分量之间“架设新通道（合并）”，是无向图演化中最频繁的操作。 如果每次连通性查询都运行一次 BFS/DFS，单次查询最坏耗时 $O(V+E)$；如果用邻接矩阵或传递闭包维护，空间开销 $O(V^2)$ 且合并代价极大。

**并查集（Disjoint Set Union, DSU）**通过树形指针将集合关系极度简化，支持几乎常数时间的集合合并与查询。

路径压缩与按秩合并的双剑合璧

1. 路径压缩（Path Compression）： 在执行 find(x) 寻找代表节点时，将递归回溯路径上的所有节点直接挂接在根节点下。
2. 按秩合并（Union by Rank / Size）： 合并两棵树时，将深度较小（或节点数较少）的树合并到深度较大（节点数较多）的树下方，防止树退化成单链。

双重优化下，单次操作的均摊时间复杂度降至严格的 $O(\alpha (N))$，其中 $\alpha (N)$ 是反阿克曼函数，对于宇宙中一切实际可能出现的数据规模，$O(\alpha (N))\le 4$，等同于绝对常数 $O(1)$！

struct DSU {
    std::vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // 路径压缩
    }

    bool unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false; // 已经处于同一连通块

        // 按秩合并
        if (rank[rootX] < rank[rootY]) std::swap(rootX, rootY);
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) rank[rootX]++;
        return true;
    }
};

最小生成树（Kruskal 算法）的贪心本质

问题：给定带权无向连通图，选出 $N-1$ 条边，使全图连通且边权总和最小。

Kruskal 算法的步骤非常优雅：

1. 将所有边按照边权从小到大排序。
2. 依次遍历每条边 $(u,v,w)$：
   • 用 DSU 检查 $u$ 和 $v$ 是否已连通。
   • 若不连通，将该边加入生成树集合，并在 DSU 中合并 $u,v$。
   • 若已连通，跳过（若加入必成环，违背树的性质且权值非最小）。
3. 收集到 $N-1$ 条边即构成全局最小生成树。

// 边结构体定义
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

long long kruskal(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total_weight = 0;
    int edges_count = 0;

    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total_weight += e.weight;
            if (++edges_count == n - 1) break;
        }
    }
    return (edges_count == n - 1) ? total_weight : -1; // -1 表示不连通
}

并查集不仅用于 MST，也是种类并查集（食物链问题）、带权并查集（相对距离维护）和动态离线连通性（按时间轴线段树分治）的不可替代的砖石基底。