正文
并查集你可以理解为是族谱森林（一开始每个节点初始化为自己），我们用 $f_i$ 表示 $i$ 的父亲，一般有以下操作：并和查。
先来说查，查就是字面意思：查找 $i$ 的最早祖先，我们可以递归查找，查找 $i$ 的父亲，再查找 $i$ 的父亲的父亲，依次递归，就有了以下代码。
int find(int x) {
if (f[x]==x) {
return x;
}
return find(f[x]);
}
但是我们发现，如果查找一个人的最早祖先，就需要付出 $O(n)$ 的时间复杂度（虽说比较小但还是不划算），所以我们就需要想另一种方法，然后我们发现，在最早祖先下的所有祖先，好像并没有什么用，所以我们可以用 $f_i$ 表示 $i$ 的最早祖先，这种方法我们称为路径压缩。
int find(int x) {
if (f[x]==x) {
return x;
}
return f[x]=find(f[x]);//路径压缩
}
再来说并，并就是把两棵族谱树连在一起，怎么连呢？很简单我们只需找到 $i$ 和 $j$ 的最早祖先，然后将其中 $i$ 的最早祖先的祖先即 $f_{find(i)}$，表示为 $j$ 即可（也可以反过来），代码如下。
void join(int x,int y) {
int nx=find(x),ny=find(y);//i、j 的最早祖先
f[nx]=ny;//并
}
拓展
我们在做并查集时，$f_i$ 一般表达的是亲戚关系，但在 P1892 中有两种关系，一种为亲戚关系，另一种为敌对关系，这就涉及到了另一个知识：反集。$i$ 的反集一般用 $f_{i+n}$ 来表示，其他的基本与并查集无异（但是在 join(i+n,j)中，两个参数千万不能写反），上代码（P1892）：
#include <iostream>
using namespace std;
int n,m,ans;
char c;
int f[2001];
int find(int x) {
if (f[x]==x) {
return x;
}
return f[x]=find(f[x]);
}
void join(int x,int y) {
int nx=find(x),ny=find(y);
if (nx!=ny) {
f[nx]=ny;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
cin>>n>>m;
for (int i=1;i<=2*n;i++) {
f[i]=i;
}
for (int i=1;i<=m;i++) {
cin>>c;
int t1,t2;
cin>>t1>>t2;
if (c=='F') {
join(t1,t2);
} else if (c=='E') {
join(t1+n,t2);
join(t2+n,t1);
}
}
for (int i=1;i<=n;i++) {
if (f[i]==i) {
ans++;
}
}
cout<<ans;
}
可以发现基本与并查集无异，只是需要多写一个 join。
如有不懂还可参考 there。
再来看一道题 P2024 ，第一眼看上去就觉得是一个反集，于是便自信的打了一个反集上去，然后，成功地连样例都没过。
………
为什么？仔细读题你会发现，题目中的关系为：$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$，已就是说 $A$ 吃 $B$，$B$ 不吃 $A$，所以反集不成立（因为这是单向关系），所以我们就素要把 $f$ 数组再开一倍（也就是开三倍）去储存关系，即 $f_i$ 表示为 $i$ 的亲戚，$f_{i+n}$ 表示为 $i$ 的猎物，$f_{i+n+n}$ 表示为 $i$ 的天敌，再使用并查集去套即可 AC，上代码：
#include <iostream>
#include <cstdio>
using namespace std;
int f[300005];
int n,k,ans;
inline int read() {//要写快读，cin 过不去
int sum=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
return sum;
}
int find(int x) {
if (x==f[x]) {
return x;
}
return f[x]=find(f[x]);
}
void join(int x,int y) {
int nx=find(x),ny=find(y);
f[nx]=ny;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int x,y,z;
n=read(),k=read();
// cin>>n>>k;
for (int i=1;i<=3*n;++i) {
f[i]=i;
}
for(int i=1;i<=k;++i)
{
z=read(),x=read(),y=read();
// cin>>z>>x>>y;
if (x>n or y>n) {
ans++;
continue;
}
if(z==1)
{
if(find(x+n)==find(y) or find(x+n+n)==find(y)) {
ans++;
} else {
join(x,y);
join(x+n,y+n);
join(x+n+n,y+n+n);
}
} else if (z==2) {
if (x==y) {
ans++;
} else if (find(x)==find(y) or find(x+2*n)==find(y)) {
ans++;
} else {
join(x,y+n+n);
join(x+n,y);
join(x+n+n,y+n);
}
}
}
printf("%d\n",ans);
return 0;
}
并查集的扩展应用实际就是开多倍的 $f$ 数组去表达关系，并没有什么难处。
题目
finally
如有不准确请纠正。
0 条评论