题目要求:
第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Zi、Xi、Yi
当Zi=1时,将Xi与Yi所在的集合合并
当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 int N,M,fa[10005]; 8 int find(int ); 9 10 void pt(int x,int y) 11 { 12 int faa=find(x); 13 int fbb=find(y); 14 if(faa==fbb)printf("Y\n"); 15 else printf("N\n"); 16 } 17 18 int find(int x) 19 { 20 int r=x; 21 while( fa[r]!=r )r=fa[r]; 22 while(x!=r){ 23 x=fa[x]; 24 fa[x]=r; 25 } 26 return r; 27 } 28 29 void ADD( int X , int Y ) 30 { 31 int faa=find(X); 32 int fbb=find(Y); 33 if( faa != fbb ){ 34 fa[faa]=fbb; 35 } 36 } 37 38 void init() 39 { 40 int X,Y,Z; 41 cin>>N>>M; 42 for(int i=1;i<=N;i++){ 43 fa[i]=i; 44 } 45 for(int j=1;j<=M;j++){ 46 scanf("%d%d%d",&Z,&X,&Y); 47 if(Z==1)ADD( X , Y ); 48 if(Z==2)pt( X , Y ); 49 } 50 } 51 52 int main() 53 { 54 init(); 55 return 0; 56 }
洛谷3367:http://www.luogu.org/problem/show?pid=3367