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 |
题意看了好久~~擦汗 其实是道并查集水题 其实就是求多少人被0感染了#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 30000+100; int par[maxn]; int rank[maxn]; //初始化 void init(int n) { for(int i=0;i<n;i++) { par[i]=i; rank[i]=0; } } int find(int x) { if(par[x]==x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x,int y) { x = find(x); y = find(y); if(x==y) return; if(rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if(rank[x]==rank[y]) rank[x]++; } } int num[maxn]; int main() { int n,m; while(cin>>n>>m) { if(n==0&&m==0) break; init(n); int z; for(int i=0;i<m;i++) { cin>>z; scanf("%d",&num[0]); for(int i=1;i<z;i++) { scanf("%d",&num[i]); unite(num[0],num[i]); } } int ans=0; for(int i=0;i<n;i++) { if(find(i)==par[0]) { ans++; } } cout<<ans<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator