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 |
变异并查集<附代码>#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define MAX 30010 long int father[MAX]; long int s[MAX]; int flag[MAX]; long int finds(long int x) { if(x!=father[x]) { father[x]= finds(father[x]); } return father[x]; } int main() { long int i,j,m,n,k,q,mas; while(scanf("%ld %ld",&m,&n)&&(n||m)) { memset(flag,0,sizeof(flag)); q= 0; for(i= 0;i<m;i++) { father[i]= i; } for(i=0;i<n;i++) { mas= 30001; scanf("%ld",&k); for(j=0;j<k;j++) { scanf("%ld",&s[j]); flag[s[j]]= 1; if(mas>finds(s[j])) { mas= finds(s[j]); } } for(j=0;j<k;j++) { father[finds(father[s[j]])]= mas; } } flag[0]= 1; for(i= 1;i<m;i++) { if(flag[i]) father[i]= finds(i); } for(i=0;i<m;i++) { if(flag[i]) { if(father[i]==0) { q++; } } } printf("%ld\n",q); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator