解题思路:
北大OJ上的一道经典并查集的题, 因为题目中说最初的学生0被视为嫌疑犯,所以只需要寻找根节点与0相等的即可。
程序代码:
#include<stdio.h> int f[30001]; int getf(int v) { if(f[v]==v) return v; else { f[v]=getf(f[v]); return f[v]; } } void merge(int v,int u) { int t1=getf(v); int t2=getf(u); if(t1!=t2) f[t2]=t1; return ; } int main() { int n,m,i,j,k,x,y,sum; while(~scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; for(i=0;i<n;i++) f[i]=i; while(m--) { scanf("%d %d",&k,&x); for(j=1;j<k;j++) { scanf("%d",&y); merge(x,y); } } sum=1; for(i=1;i<n;i++) { if(getf(i)==getf(0)) sum++; } printf("%d\n",sum); } return 0; }