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 |
帮你用小号交了一下,把cin改scanf就过了>_<In Reply To:Re:急需有人帮我看看1611并查集,为什么会超时啊 Posted by:crazyyangdan at 2011-06-05 11:01:56 #include<stdio.h> using namespace std; int parent[30001],num[30001],root1,root2; void set(int i) { parent[i]=i; num[i]=1; } int find(int a) { if(parent[a]==a) return a; parent[a]=find(parent[a]); return parent[a]; } void uni(int a,int b) { root1=find(a); root2=find(b); if(root1==root2) return; if(num[root1]>=num[root2]) { parent[root2]=root1; num[root1]+=num[root2]; } else { parent[root1]=root2; num[root2]+=num[root1]; } } int main() { int first,next,i,j,m,n,k; while(1) { scanf("%d %d",&m,&n); if(m+n==0) break; for(i=0;i<m;i++) set(i); for(j=0;j<n;j++) { scanf("%d%d",&k,&first); for(int z=1;z<k;z++) { scanf("%d",&next); uni(first,next); } }printf("%d\n",num[find(0)]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator