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> using namespace std; int father[30002]; int sum[30002]; int getfather(int v) { if(father[v]==v) return v; return father[v] = getfather(father[v]); } void connect(int x,int y) { int fx,fy; fx = getfather(x); fy = getfather(y); if(fx==fy)return; sum[fy] = sum[fx]+sum[fy]; father[fx] = fy; } int main() { int n,m; int i,num,fath; while(cin>>n>>m) { if(!n && !m)break; for(i=0;i<=n;i++) { father[i] = i; sum[i] = 1; } while(m--) { cin>>num; cin>>fath; num--; while(num--) { cin>>i; if(father[i]!=father[fath]) connect(i,fath); } } cout<<sum[getfather(0)]<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator