3269224138刘 @ 2017-03-15 10:42:12
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int j,aa,num,i,d,x,y,p,m,q,a[10012],n;
int find(int i){
j=i;
while (a[j]!=0)
j=a[j];
return(j);
}
int main(){
scanf("%d %d",&n,&m);
for (i=1;i<=m;++i)
{
scanf("%d%d%d",&d,&x,&y);
p=find(x);
q=find(y);
if (d==1)
if (p!=q)
a[q]=p;
if (d==2)
{
if (p==q)
printf("%s\n","Y");
else
printf("%s\n","N");
}
}
return 0;
}by Tom_com @ 2017-03-23 18:44:29
int find(int i)
{
if(a[i]!=i) a[i]=find(a[i]);
return a[i];
}by Lyrics @ 2017-07-23 15:06:59
应该考虑一下路径压缩问题。直接把你要合并的那个点指向别人就行了。
- p=find(x);
- q=find(y);
- a[q]=p;
- a[x]=p
这样的话会更加保险一些