并查集CSP-S

💡 核心思想

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

🎯 直觉理解

并查集解决"两个元素是否在同一集合"和"合并两个集合"，两种操作都近似 $O(1)$。它就像班级里的"认亲"：每个人记住自己的"组长"，问两个人是不是一伙的，就顺着组长链往上找，看最终的老大是不是同一个。

两个关键优化：路径压缩（找完老大后，把沿途所有人的组长直接改成老大，下次查找一步到位）和按秩合并（矮树接高树，防止链退化）。

经典应用：判连通块（图里有多少个连通分量）、Kruskal 判环、带权并查集解决"关系传递"类问题（如食物链）。实现只有三个函数：find、union、init。

📝 算法流程

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

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

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

📊 复杂度分析

💻 参考实现（C++）

#include 
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;
}

⚠️ 常见坑点

📚 相关题目