此题是一个并查集的应用题,也不难,只是有一个不太常用的操作——并查集的换根操作。
观察题目,发现3个操作分别是
- 将两个集合合并,并将新集合的代表元素设为第二个集合的代表元素
- 将一个集合的代表元素换成另一个
- 查询一个集合的代表元素
其中1、3两个操作是可以用并查集轻松实现的(根结点为代表元素即可),但是2操作就不太好做了,这也是本题的重点——换根。
换根意思就是将并查集的根换为另一个节点 废话,字面都能看出来,那如何操作呢?看下面这个图
看了这个图,换根操作也不难李姐理解了,用代码写出来就是这样的
int pa=find(a);
p[pa]=a,p[a]=a;
剩下代码就留给大家自行补齐
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[100010];
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void turn_root(int a)
{
int pa=find(a);
p[pa]=a,p[a]=a;
}
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i++)p[i]=i;
while(m--){
int t,a,b;
cin>>t>>a;
if(t==1){
cin>>b;
int pa=find(a),pb=find(b);
p[pa]=pb;
}
else if(t==2)turn_root(a);
else cout<<find(a)<<endl;
}
}