简单并查集
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 using namespace std; 8 int fa[1010],r[1010]; 9 int find(int x) 10 { 11 if(fa[x]!=x) 12 fa[x] = find(fa[x]); 13 return fa[x]; 14 } 15 int main() 16 { 17 int i,u,v; 18 int flag = 0; 19 for(i = 1; i <= 1000 ; i++) 20 { 21 fa[i] = i; 22 r[i] = 0; 23 } 24 while(cin>>u>>v) 25 { 26 int x = find(u),y = find(v); 27 if(x!=y) 28 { 29 fa[x] = y; 30 r[y]+=r[x]+1; 31 } 32 else 33 r[y]+=1; 34 } 35 for(i = 1; i <= 1000 ; i++) 36 { 37 int x = find(i); 38 if(r[i]==1) 39 continue; 40 if(x==i) 41 { 42 if(r[i]%2!=0) 43 { 44 flag = 1; 45 break; 46 } 47 } 48 } 49 if(!flag) 50 printf("1 "); 51 else 52 printf("0 "); 53 return 0; 54 }