并查集CSP-S

💡 核心思想

并查集（Disjoint Set Union, DSU）用于维护不相交集合的合并与查询。核心操作：find（查找根/代表元素）和 unite/merge（合并两个集合）。加上路径压缩和按秩合并后，每次操作接近 $O(1)$。

🎯 直觉理解

并查集就像"帮派"系统。每个人有一个"老大"，老大就是帮派的代表。你要知道两个人是否在同一个帮派，就看他们的"最终老大"是不是同一个人。路径压缩就是：不管中间经过多少层，直接告诉每个人他的最终老大是谁，以后查得更快。

📝 算法流程

1. 初始化：每个元素是自己的集合
2. find：沿 parent 向上找根，路径压缩
3. unite：将两个集合的根合并
4. 可维护集合大小、到根的距离等附加信息

$$\text{路径压缩 + 按秩合并：} O(\alpha(n)) \approx O(1)$$

$$\alpha \text{ 是反阿克曼函数，增长极慢}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int fa[100005], rnk[100005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    fa[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
}
int main() {
    int n, m; cin >> n >> m;
    iota(fa, fa+n+1, 0);
    memset(rnk, 0, sizeof(rnk));
    while (m--) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) unite(x, y);
        else cout << (find(x)==find(y)?"Y":"N") << "\n";
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目