并查集
Summary
并查集 & 扩展域并查集 & 边带权并查集.
Links
三道模板题:
- [P3367 [模板]并查集](https://www.luogu.org/problemnew/show/P3367)
- [P2024 [NOI2001]食物链](https://www.luogu.org/problemnew/show/P2024)
- [P1196 [NOI2002]银河英雄传说](https://www.luogu.org/problemnew/show/P1196)
Text
并查集思想
最开始 a,b,c... 等元素分别在不同的集合中,f[a]=a,f[b]=b,f[c]=c... 现在将 a,b 所在的集合合并, 使 f[a]= b 这样 a 与 b 的 f[]都是 b, 也就是在同一个集合中了.
所以可以认为当 f[a]==f[b]时 a,b 在同一个集合中.
但是很容易就会出现以下两种问题:
- a,b 已经在同一个集合中, 且 f[a]=f[b]=b, 现在想要合并 a,c, 就会导致 f[a]=f[c]=c,f[b]= b 的错误;
- a,b 已经在同一个集合中, 且 f[a]=f[b]=b, 现在想要合并 c,a, 就会导致 f[a]=f[b]=b,f[c]=c, 在判断 a,b 与 c 是否在同一集合中时会出现问题.
所以我们定义find()函数:
int find(int now)
{
return f[now] == now ? now : find(f[now]);
}, 并将合并操作改为 f[find(a)]=find(b), 即可避免上述问题 (因为这样是直接合并了最久远的祖先).
现在出现了第三个问题:
- 先合并 a,b, 再合并 b,c, 再合并 c,d... 就会使 f[a]=b,f[b]=c,f[c]=d...
find()函数效率就会变得很低, 接近 O(n).
解决方法是路径压缩 (或启发式合并 / 按秩合并, 暂时先咕), 修改find()函数:
int find(int now)
{
return f[now] == now ? now : f[now] = find(f[now]);
}, 分析:
1. 如果当前节点的 f[] 就是自己 (
f[now]==now), 则返回自己 (return now);2. 否则 (
f[now]!=now) 将 f[] 改为最终的祖先 (f[now]=find(f[now]), 这段代码的返回值为find(f[now])), 并返回最终祖先 (return find(f[now])).
.
并查集
由之前的分析可以做出第一道例题 ([P3367 [模板] 并查集](https://www.luogu.org/problemnew/show/P3367)),注意在程序开头必须使所有 f[i]=i.
Code:
#include <cstdio>
using namespace std;
int n, m, x, y, z, f[10005];
int find(int now)
{
return f[now] == now ? now : f[now] = find(f[now]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
f[i] = i;
while (m--)
{
scanf("%d%d%d", &z, &x, &y);
if (z - 1)
printf("%c\n", find(x) == find(y) ? 'Y' : 'N');
else
f[find(x)] = find(y);
}
return 0;
}扩展域并查集
先看第二道例题 ([P2024 [NOI2001] 食物链](https://www.luogu.org/problemnew/show/P2024)).
由题面可以看出:
- 若 X 和 Y 是同类, 则 X 和 Y,X 的食物和 Y 的食物,X 的天敌和 Y 的天敌分别相同;
- 若 X 吃 Y, 则 X 和 Y 的天敌,X 的食物和 Y,X 的天敌和 Y 的食物分别相同.
即 当输入1 X Y时, 合并 X 和 Y,X 的食物和 Y 的食物,X 的天敌和 Y 的天敌, 输入2 X Y时, 合并 X 和 Y 的天敌,X 的食物和 Y,X 的天敌和 Y 的食物 .
同时在处理每句话之前也要先判断真假, 以下信息会出现矛盾:
当输入
1 X Y时- X 与 Y 的食物在同一集合(X 吃 Y).
- X 的食物与 Y 在同一集合(Y 吃 X).
当输入
1 X Y时- X 与 Y 在同一集合 (X 和 Y 是同类).
- X 与 Y 的食物在同一集合 (Y 吃 X).
Code:
#include <cstdio>
using namespace std;
int n, k, cnt, in1, in2, in3, f[150020];
int find(int now)
{
if (now == f[now])
return now;
return f[now] = find(f[now]);
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = n * 3; i > 0; i--)
f[i] = i;
while (k--)
{
scanf("%d%d%d", &in1, &in2, &in3);
if (in2 > n || in3 > n)
{
cnt++;
continue;
}
if (in1 == 1)
{
if (find(in2 + n) == find(in3) || find(in2) == find(in3 + n))
cnt++;
else
{
f[find(in2)] = find(in3);
f[find(in2 + n)] = find(in3 + n);
f[find(in2 + n + n)] = find(in3 + n + n);
}
}
else
{
if (find(in2) == find(in3) || find(in2) == find(in3 + n))
cnt++;
else
{
f[find(in2)] = find(in3 + n + n);
f[find(in2 + n)] = find(in3);
f[find(in2 + n + n)] = find(in3 + n);
}
}
}
printf("%d", cnt);
return 0;
}边带权并查集
第三道例题 ([P1196 [NOI2002] 银河英雄传说](https://www.luogu.org/problemnew/show/P1196))就是一个典型的边带权并查集, 此类并查集的find()函数除了要处理 f[] 外还要处理其他附加信息, 具体思路看该题目题解即可.
Code:
#include <cstdio>
#include <cstdlib>
using namespace std;
int t, in1, in2, f[30005], l[30005], s[30005];
char c;
int find(int now)
{
if (now == f[now])
return now;
int fnow = f[now];
f[now] = find(f[now]);
l[now] += l[fnow];
s[now] = s[f[now]];
return f[now];
}
int main()
{
for (int i = 1; i <= 30000; i++)
f[i] = i, s[i] = 1;
scanf("%d\n", &t);
while (t--)
{
c = getchar(), scanf("%d%d\n", &in1, &in2);
if (c == 'M')
{
int f1 = find(in1), f2 = find(in2);
if (f1 == f2)
continue;
f[f1] = f2;
l[f1] += s[f2];
s[f1] = s[f2] = s[f1] + s[f2];
}
else
{
int f1 = find(in1), f2 = find(in2);
printf("%d\n", f1 == f2 ? abs(l[in1] - l[in2]) - 1 : -1);
}
}
return 0;
}