Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
不压缩路径是500+MS,附代码#include<cstdio> int n,m,p[30005],a[30005]; void ini() { int i; for(i=0;i<n;i++)p[i]=i; } int find(int x) { while(p[x]!=x)x=p[x]; return x; } int find2() { int count=1,i; for(i=1;i<n;i++) if(find(0)==find(i))count++; return count; } void combine(int x,int y) { x=find(x); y=find(y); p[x]=y; } int main() { int t,i,j; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; ini(); for(i=1;i<=m;i++) { scanf("%d",&t); for(j=1;j<=t;j++) { scanf("%d",a+j); } for(j=2;j<=t;j++) { combine(a[j-1],a[j]); } } printf("%d\n",find2()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator