【寻迹#4】并查集
并查集
一、简介
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
顾名思义，并查集支持两种操作：
- 合并（Union）：合并两个元素所属集合（合并对应的树）
- 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
1.初始化
所有的元素在初始时默认在单独的集合内，表示为只有一颗根节点的树， 方便起见，我们将根节点的父亲设为自己。
2.查询
我们需要沿着树向上移动，直到找到根节点。
这个过程中可以采用路径压缩，即并查集维护的是很多个集合，对树的形状并没有要求，可以直接将所有节点连接到树的根节点。
3.合并
要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。
3.1启发式合并
合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。
即每次合并前比较一下树的节点数。
4.删除
要删除一个叶子节点，我们可以将其父亲设为自己。为了保证要删除的元素都是叶子，我们可以预先为每个节点制作副本，并将其副本作为父亲。
void erase(int x)
{
int xx=Find(x);
--size[xx];
fa[x] = x;
}
5.移动
与删除类似，通过以副本作为父亲，保证要移动的元素都是叶子。
void move(int x,int y)
{
int fx=Find(x);int fy=Find(y);
if(fx==fy) return;
fa[x]=fy;
--size[fx];++size[fy];
}
6.带权并查集
我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。
7.其他应用
最小生成树算法中的 Kruskal 和 最近公共祖先中的 Tarjan 算法是基于并查集的算法。
二、题单
1.修复公路
传送门
思路：最小生成树模板题，主要体现一下并查集的应用
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 1050
#define M 100050
struct E{ int x,y,z; }edge[M];
int n,m;
int fa[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar(); }
while(ch>='0'&&ch<='9') { x=x*10+ch-48;ch=getchar(); }
return x*f;
}
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
inline bool cmp(E a, E b) { return a.z<b.z; }
int Find(int x)
{
if(x==fa[x]) return x;
return fa[x]=Find(fa[x]);
}
inline int kruskal()
{
int num=0,maxx=0;
for(int i=1;i<=m;i++)
{
int x=edge[i].x;int y=edge[i].y;int z=edge[i].z;
x=Find(x);y=Find(y);
if(x==y) continue;
fa[x]=y;num++;
maxx=max(maxx,z);
if(num==n-1) break;
}
if(num==n-1) return maxx;
return -1;
}
int main()
{
n=read();m=read();
init(n);
for(int i=1;i<=m;i++) { edge[i].x=read();edge[i].y=read();edge[i].z=read(); }
sort(edge+1,edge+1+m,cmp);
cout<<kruskal()<<endl;
return 0;
}
2.奶酪
传送门
思路：
用并查集维护。
对于每一个点，先判断是否与上表面或下表面联通，
再遍历之前的点，把所有相交的点（球）扔到一个集合里，
最后遍历上表面和下表面的点，看看能否找到一条通道。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 10500
int T,n,cnt1,cnt2;
ll h,r;
int fa[N],f1[N],f2[N];
struct node{ ll x,y,z; }a[N];
inline void init(int n)
{
memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));
cnt1=cnt2=0;
for(int i=1;i<=n;i++) fa[i]=i;
}
inline ll dist(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2) { return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2); }
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
cin>>h>>r;
init(n);
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
for(int i=1;i<=n;i++)
{
ll x1=a[i].x;ll y1=a[i].y;ll z1=a[i].z;
if(z1+r>=h) f1[++cnt1]=i;
if(z1-r<=0) f2[++cnt2]=i;
for(int j=1;j<=i;j++)
{
ll x2=a[j].x;ll y2=a[j].y;ll z2=a[j].z;
if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)>4*r*r) continue;
if(dist(x1,y1,z1,x2,y2,z2)<=4*r*r)
{
int fax=Find(i);int fay=Find(j);
if(fax!=fay) fa[fax]=fay;
}
}
}
int book=0;
for(int i=1;i<=cnt1;i++)
for(int j=1;j<=cnt2;j++) if(Find(f1[i])==Find(f2[j])) book=1;
if(book) puts("Yes");
else puts("No");
}
return 0;
}
3.程序自动分析
传送门
思路：
其实是一道比较好想的并查集的问题，
考虑先把所有约束条件按照 \(e\) 排序，
如果 \(e=1\) 就把两个点连起来，
如果 \(e=0\) 时发现这两个点已经连起来了，那就可以直接认为无法满足，
但本题的关键在于，数据过大，直接开数组可能会越界，所以需要离散化。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 200050
int T;
struct P{ int x,y,z; }a[N];
int temp[N],fa[N];
int n,m;
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
int Find(int x)
{
if(fa[x]==x) { return x; }
return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
inline int check(int x,int y) { return Find(x)==Find(y); }
inline bool cmp(P a,P b) { return a.z>b.z; }
int main()
{
cin>>T;
while(T--)
{
int tot=0;
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i].x>>a[i].y>>a[i].z;
temp[++tot]=a[i].x;temp[++tot]=a[i].y;
}
sort(temp+1,temp+1+tot);
n=unique(temp+1,temp+1+tot)-(temp+1);
for(int i=1;i<=m;i++)
{
a[i].x=lower_bound(temp+1,temp+1+n,a[i].x)-temp;
a[i].y=lower_bound(temp+1,temp+1+n,a[i].y)-temp;
}
init(n);
sort(a+1,a+1+m,cmp);
int book=0;
for(int i=1;i<=m;i++)
{
if(a[i].z) Link(a[i].x,a[i].y);
else if(check(a[i].x,a[i].y)) { book=1;break; }
}
if(book) puts("NO");
else puts("YES");
}
return 0;
}
4.关押罪犯
传送门
思路：
首先想到将事件的影响力排序，这样发生的第一件冲突即为最后的答案，
那么从上到下考虑没一起事件，肯定是优先不让它发生，即把两个罪犯分到两个监狱中去，
重复此操作，直到有两个罪犯被迫相遇产生冲突。
将并查集开为两倍大小，设两个罪犯为 \(x\) 和 \(y\) ，
如果当前 \(x\) 与 \(y\) 已经处于一个集合中，则无法避免冲突，直接输出答案即可，
否则的话将 \(x\) 与 \(y+n\) 放在一个集合中， \(y\) 与 \(x+n\) 放在一个集合中。
代码：
#include<bits/stdc++.h>
using namespace std;
#define M 100050
#define N 20050
struct I{ int a,b,c; }inc[M];
int fa[N*2];
int n,m,book;
inline bool cmp(I x,I y) { return x.c>y.c; }
inline void init(int n) { for(int i=1;i<=2*n;i++) fa[i]=i; }
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
inline int check(int x,int y) { return Find(x)==Find(y); }
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
int main()
{
cin>>n>>m;
init(n);
for(int i=1;i<=m;i++) cin>>inc[i].a>>inc[i].b>>inc[i].c;
sort(inc+1,inc+1+m,cmp);
for(int i=1;i<=m;i++)
{
int x=inc[i].a;int y=inc[i].b;int z=inc[i].c;
if(check(x,y)) { book=1;cout<<z<<endl;break; }
Link(x,y+n);
Link(y,x+n);
}
if(!book) puts("0");
return 0;
}
5.食物链
传送门
思路：
与上一道关押罪犯类似，
考虑开三个集合 \(A,B,C\) ，每个集合中都有 \(1\sim n\) 的点，不妨假设 \(A\) 吃 \(B\) ， \(B\) 吃 \(C\) ， \(C\) 吃 \(A\) ，
先考虑并查集的维护，判断假话我们后面再说，
当读取到是 \(x\) 和 \(y\) 同类的指令时，要将 \(A,B,C\) 集合中的 \(x\) 和 \(y\) 点都连接起来，因为我们并不知道 \(x\) 和 \(y\) 具体属于哪一个集合，
当读取到 \(x\) 吃 \(y\) 的指令时，我们要连接 \(A\) 中的 \(x\) 和 \(B\) 中的 \(y\) ， \(B\) 中的 \(x\) 和 \(C\) 中的 \(y\) ，依此类推…
再来说如何判断真假，
当读取到 \(x\) 和 \(y\) 是同类的指令时，我们只需要判断 \(x\) 和 \(y\) 是否有吃或者被吃的关系，如果有那么就是假话
当读取到 \(x\) 吃 \(y\) 的指令时，要先判断如果 \(x=y\) ，那么这句话是假话；如果\(x\) 和 \(y\) 是同类，那么这句话也是假话；如果 \(y\) 吃 \(x\) ，那么这句话也是假话
最后要特判如果有大于 \(n\) 的点也要算假话。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 50050
int n,k;
int cnt;
int fa[N*3];
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
inline int check(int x,int y) { return Find(x)==Find(y); }
int main()
{
cin>>n>>k;
init(3*n);
int Type,x,y;
for(int i=1;i<=k;i++)
{
cin>>Type>>x>>y;
if(x>n||y>n){ cnt++;continue; }
if(Type==1)
{
if(check(x,y+n)||check(x,y+2*n)) { cnt++;continue; }
//第一个括号：(x,y+n) or (x+n,y+2*n) or (x+2*n,y)三个都可以 第二个括号：(x+n,y) or (x+2*n,y+n) or (x,y+2*n) 三个都可以
Link(x,y);
Link(x+n,y+n);
Link(x+2*n,y+2*n);
}
else
{
if(x==y) { cnt++;continue; }
if(check(x,y)||check(y,x+n)) { cnt++;continue; } //check(y,x+n) or check(y+n,x+2*n) or check(y+2*n,x) 三个都可以
Link(x,y+n);
Link(x+n,y+2*n);
Link(x+2*n,y);
}
}
cout<<cnt<<endl;
return 0;
}
6.星球大战
传送门
思路：
考虑我们不好模拟点被炸毁的过程，
所以想到反过来，模拟把所有点连接起来的过程，比较难想，但是比较好实现。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
#define M 400050
#define N 400050
int ver[M],Next[M],head[N],tot=-1;
int brok[N],vis[N],ans[N],fa[N];
int cnt;
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
inline void ADD(int x,int y)
{
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
int main()
{
cin>>n>>m;
init(n);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
ADD(x,y);ADD(y,x);
}
cin>>k;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
brok[i]=x;
vis[x]=1;
}
cnt=n-k;
for(int x=0;x<n;x++)
{
for(int i=head[x];~i;i=Next[i])
{
int y=ver[i];
if(!vis[x]&&!vis[y])
{
int xx=Find(x);int yy=Find(y);
if(xx!=yy) {Link(xx,yy);cnt--;}
}
}
}
ans[k+1]=cnt;
for(int j=k;j>=1;j--)
{
int x;
x=brok[j];
cnt++;
vis[x]=0;
for(int i=head[x];~i;i=Next[i])
{
int y=ver[i];
if(!vis[y])
{
int xx=Find(x);int yy=Find(y);
if(xx!=yy) { Link(xx,yy);cnt--; }
}
}
ans[j]=cnt;
}
for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
return 0;
}
7.银河英雄传说
传送门
思路：
带权并查集的应用，除了正常的并查集之外，
我们需要维护每一个节点下的战舰数，以及一棵树下任何一个节点到它的最高父节点的距离（战舰数），
然后最后减一减答案就出来了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 30050
int fa[N],size[N],dist[N];//size[i] 维护的是编号为 i 的战舰后面有多少战舰;
//dist[i]表示的是 i 到 fa[i] or Find(i) 的战舰数
int T;
char ch;
int x,y,ans;
inline void init()
{
for(int i=1;i<=N;i++) fa[i]=i;
for(int i=1;i<=N;i++) size[i]=1;
}
int Find(int x)
{
if(fa[x]==x) return x;
int root=Find(fa[x]);
dist[x]+=dist[fa[x]];
return fa[x]=root;
}
inline void Link(int x,int y)
{
x=Find(x);y=Find(y);
fa[x]=y;
dist[x]=size[y];
size[y]+=size[x];
}
inline int check(int x,int y) { return Find(x)==Find(y); }
int main()
{
init();
cin>>T;
while(T--)
{
cin>>ch>>x>>y;
if(ch=='M') Link(x,y);
else if(!(check(x,y))) puts("-1");
else
{
ans=abs(dist[x]-dist[y])-1;
cout<<ans<<endl;
}
}
return 0;
}
8.MooTube
传送门
思路：
发现题目没有强制在线，所以可以离线操作，
于是想到可以对边的信息和查询的信息进行从大到小的排序，
对于每一次询问，只考虑建立边权比 \(k_i\) 大的边（因为小的没用，不会贡献此次询问的答案），
并且，每一次询问只需要在已有的图上继续连边即可，复杂度虽然是 \(O(nT)\) ，但是显然跑不满，
每次连边用一个数组维护连通块中节点的数量，最后减去自己即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 100050
struct edge{ int x,y,z; }a[N];
struct query{ int k,v,num; }q[N];
int n,T;
int fa[N],cnt[N],ans[N];
inline bool cmp1(edge a,edge b) { return a.z>b.z; }
inline bool cmp2(query a,query b) { return a.k>b.k; }
inline void init()
{
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++) cnt[i]=1;
}
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y)
{
int xx=Find(x);int yy=Find(y);
if(xx!=yy)
{
fa[xx]=yy;
cnt[yy]+=cnt[xx];
}
}
int main()
{
cin>>n>>T;
init();
for(int i=1;i<n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
for(int i=1;i<=T;i++)
{
cin>>q[i].k>>q[i].v;
q[i].num=i;
}
sort(a+1,a+1+(n-1),cmp1);
sort(q+1,q+1+T,cmp2);
int pos=1;
for(int i=1;i<=T;i++)
{
for(int j=pos;j<n;j++)
{
if(a[j].z<q[i].k) break;
Link(a[j].x,a[j].y);
pos++;
}
ans[q[i].num]=cnt[Find(q[i].v)]-1;
}
for(int i=1;i<=T;i++) cout<<ans[i]<<endl;
return 0;
}
9.UVA11987 Almost Union-Find
传送门
思路：
读完题目感觉比较板子，唯一比较难处理的是移动某一个元素，
因为如果移动的是根节点，那么直接修改 fa 数组必然是错误的，
因为以它为根的所有节点都被修改了，
所以我们考虑设虚根，即初始状态下每个节点 \(i\) 的根都是 \(i+n\) ，
根据路径压缩，我们所有的 \(1-n\) 的节点都不会是根节点，直接移动即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 100050
typedef long long ll;
int n,m;
int k,p,q;
int fa[2*N],size[2*N];
ll sum[2*N];
inline void init()
{
for(int i=1;i<=n;i++) fa[i]=i+n;
for(int i=n+1;i<=n+n;i++)
{
fa[i]=i;
size[i]=1;
sum[i]=i-n;
}
}
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y)
{
fa[x]=y;
size[y]+=size[x];
sum[y]+=sum[x];
}
inline void move(int x,int y,int k)
{
fa[k]=y;
size[x]--;size[y]++;
sum[x]-=k;sum[y]+=k;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
while(m--)
{
cin>>k;
if(k==1)
{
cin>>p>>q;
int x=Find(p);int y=Find(q);
if(x==y) continue;
Link(x,y);
}
else if(k==2)
{
cin>>p>>q;
int x=Find(p);int y=Find(q);
if(x==y) continue;
move(x,y,p);
}
else
{
cin>>p;
cout<<size[Find(p)]<<" "<<sum[Find(p)]<<endl;
}
}
}
return 0;
}