张曜玺 @ 2017-10-29 21:27:04
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int father[10000],rank[10000];
int find1(int x)//路径压缩递归版(易爆栈)
{
if(father[x]!=x) father[x]=find1(father[x]);
return father[x];
}
int find2(int x)//路径压缩非递归版
{
int k,j,r=x;
while(r!=father[r])
r=father[r];
k=x;
while(r!=r)
{
j=father[k];
k=j;
}
return r;
}
void un(int x,int y)//按秩合并
{
int r1=find2(x),r2=find2(y);
if(r1==r2)return ;
if(rank[x]<rank[y])//低的连到高的上
father[x]=y;
else {
father[y]=x;
if(rank[x]==rank[y])rank[x]++;
}
}
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++)
father[i]=i;
for (int i=1;i<=m;i++)
{
int bo,a,b;
cin>>bo>>a>>b;
if(bo==1)
{
un(a,b);
}
if(bo==2)
{
if(find2(a)==find2(b))
{
cout<<'Y'<<endl;
}
else{
cout<<'N'<<endl;
}
}
}
by VenusM1nT @ 2017-10-29 22:21:58
#include<cstdio>
int a,b,f[100005],n,m,p,c;
bool flag;
int find(int x)
{
if(x!=f[x])
{
f[x]=find(f[x]);
return f[x];
}
else return x;
}
int main()
{
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=p;i++)
{
scanf("%d%d%d",&c,&a,&b);
if(c==1) f[find(a)]=f[find(b)];
else if(c==2)
{
if(find(a)==find(b)) printf("Y\n");
else printf("N\n");
}
}
return 0;
}
这样就可以啊
by Uppk @ 2017-11-01 22:05:06
un函数中应该是把r1或r2的father改变再把作为祖先的那个father[r1/2]+=father[r2/1]吧