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<cstring> #include<cstdio> using namespace std; const int N=50005; int pre[N]; int num[N]; void init(int n) { for(int i=0;i<n;i++) { pre[i]=i; num[i]=1; } } int Find(int x) { int r = x; while(pre[r] != r) r = pre[r]; int t = x; while(t != r) { int j = pre[t]; pre[t] = r; t = j; } return r; } void Join(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy) { pre[fx]=fy; num[fy]+=num[fx]; } } int main() { int n,m,i,j,t,x,y; while(~scanf("%d%d",&n,&m)) { if(n==0 && m==0) { break; } init(n); for(i=0;i<m;i++) { scanf("%d",&t); scanf("%d",&x); for(j=1;j<t;j++) { scanf("%d",&y); Join(x,y); x=y; } } int x=Find(0); printf("%d\n",num[x]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator