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 |
第一个并查集,1A,16MS,附代码#include<iostream> #define SIZE 30001 using namespace std; int n,m,k,a[SIZE]={0},b[SIZE]={0}; void Init(void) { for(int i=0;n-i>0;i++) a[i]=i; } int getFather(int n) { if(a[n]!=n) return a[n]=getFather(a[n]); else return a[n]; } void Union(int x,int y) { int f_x=getFather(x); int f_y=getFather(y); a[f_x]=f_y; } int getCount(void) { int count=1; for(int i=1;n-i>0;i++) { if(getFather(i)==getFather(0)) count++; } return count; } int main() { while(scanf("%d %d",&n,&m),n||m) { Init(); for(int i=0;m-i>0;i++) { scanf("%d",&k); for(int j=0;k-j>0;j++) scanf("%d",&b[j]); for(int j=1;k-j>0;j++) Union(b[j-1],b[j]); } printf("%d\n",getCount()); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator