很抱歉这篇博客晚来了(该放在Kruskal前面的)......

并查集，故名思意，就是用来高效进行合并、查询集合的数据结构，为了方便，我们可以把每一个结点看成树形结构即可。

1.查询

Q1：我们该如何查询某一个结点在哪一个集合呢？

A1：我们知道如果需要区分开所有集合，就应该用一个代表来表示这个集合，在这里，我们把这个集合的根节点看作那个代表即可。

Q2：我们该如何判断两个结点 \(x,y\) 是否在一个集合呢？

A2：我们可以从 \(x,y\) 不停往上递归，只要遍历到那个根节点代表即可。

Q3：如何递归？

A3：我们设 \(fa_x\) 为 \(x\) 的父亲，然后将根节点 \(root\) 的 \(fa_{root}\) 设为 \(root\) ，然后我们不停往上递归，判断这个结点的 \(fa\) 值是否为本身即可。

code:

int find(int x)
{
    if(fa[x] == x) return x;
    return find(fa[x]);
}

但是我们发现如果这个集合是一条链的话，如图：

(图来来自菜鸟）

时间复杂度会退化成 \(O(n)\) ，那么这时候我们就要采用路径压缩来做，每做一次，就将 \(fa_x=root\),这样后面继续进行查找时间复杂度就会成为优秀的 \(O(1)\)

code:

int find(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

2.合并

Q1:如何合并 \(x,y\) 两个集合?

A1:将 \(x\) 集合的根节点拉一条边朝向 \(y\) 集合的祖先。

code:

void merge(int x,int y)
{
    fa[find(x)] = find(y);
}

习题

接下来我们通过一些习题来认识一些特殊的并查集

1.P3367 【模板】并查集

普通并查集，套用刚刚的模板即可。

2.P1196 [NOI2002] 银河英雄传说

带权并查集，我们设 \(d_i\) 为 \(i\) 到此集合根节点的距离，由于统计的是边的数量，所以我们最后统计答案的时候要将他变为 \(d_b-d_a-1\)。

(1)查询的变化

当我们没有迭代到根节点的时候，首先弄出根节点 \(root\) ，然后将 \(d_x\) 加上 \(d_{fa_x}\) ，接着再路径压缩

int find(int x)
{
    if(fa[x] != x)
    {
        int root = find(fa[x]);
        d[x] += d[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

(2)合并的变化

我们再维护一个 \(siz\) 数组，当 \(x\) 和 \(y\) 所在的集合要合并时，先按照模板合并，然后将两个集合的 \(siz\) 值相加，接着 \(d_{rootx} = siz_{rooty}\) 即可(距离 \(rooty\) 的距离为 \(rootx\))

if(fia != fib)
{
    fa[fia] = fib;
    d[fia] = sz[fib];
    sz[fib] += sz[fia];
}

3.P2024 [NOI2001] 食物链

扩展域并查集

我们弄 \(3\) 个集合，对于任意一个结点 \(i\) :

1 \(i\) 表示本身

2 \(i+n\) 表示 \(i\) 的天敌

3 \(i+2n\) 表示 \(i\) 的猎物

后面两个情况直接特判即可，第一种情况：

如果 \(x\) 和 \(y\) 是同类，若 \(x\) 是 \(y\) 的天敌或猎物，那么是假话。
如果 \(x\) 吃 \(y\)，若 \(x\) 和 \(y\) 是同类，那么是假话。
如果 \(x\) 吃 \(y\)，若 \(x\) 是 \(y\) 的猎物，那么是假话。
如果 \(x\) 吃 \(y\)，若 \(y\) 是 \(x\) 的天敌，那么是假话。

代码就不放了。