首页 > 代码库 > 【裸的并查集】POJ 1611 The Suspects
【裸的并查集】POJ 1611 The Suspects
http://poj.org/problem?id=1611
【Accepted】
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include <string> 6 using namespace std; 7 const int maxn=3e4+3; 8 int fa[maxn]; 9 int n,m; 10 int a[maxn]; 11 12 void init() 13 { 14 for(int i=0;i<n;i++) 15 { 16 fa[i]=i; 17 } 18 } 19 int find(int x) 20 { 21 return x==fa[x]?x:fa[x]=find(fa[x]); 22 } 23 24 void mix(int x,int y) 25 { 26 int fx=find(x); 27 int fy=find(y); 28 if(fx!=fy) 29 { 30 fa[fx]=fy; 31 } 32 } 33 34 int main() 35 { 36 while(~scanf("%d%d",&n,&m)) 37 { 38 if(n==0&&m==0) 39 { 40 break; 41 } 42 init(); 43 for(int i=0;i<m;i++) 44 { 45 int k; 46 scanf("%d",&k); 47 if(k>=1) 48 { 49 scanf("%d",&a[0]); 50 for(int j=1;j<k;j++) 51 { 52 scanf("%d",&a[j]); 53 mix(a[0],a[j]); 54 } 55 } 56 } 57 int sum=0; 58 for(int i=0;i<n;i++) 59 { 60 if(find(i)==fa[0]) 61 { 62 sum++; 63 } 64 } 65 printf("%d\n",sum); 66 } 67 return 0; 68 }
【不太明白】
为啥find(i)==fa[0]能A,fa[i]==fa[0]就是WA。find(0)一定等于fa[0]?
【裸的并查集】POJ 1611 The Suspects
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。