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 |
苍天呐!!为毛一直wa!!!!#include <iostream> #include <string> #include <cstdio> using namespace std; #define N 300005 int parent[N], rank[N]; void this_init() { memset(parent, -1, sizeof(parent)); memset(rank, -1, sizeof(rank)); } void make_set(int x) { parent[x] = x; rank[x] = 1; } int find_set(int x) { if (x != parent[x]) { parent[x] = find_set(parent[x]); } return parent[x]; } void link_set(int x, int y) { if (rank[x] > rank[y]) { parent[y] = x; rank[x] += rank[y]; } else { parent[x] = y; rank[y] += rank[x]; } } void union_set(int x, int y) { link_set(find_set(x), find_set(y)); } int main() { int n,m,i,j,k; this_init(); while (cin >> n >> m) { if (n==0 && m==0) { break; } for (i=0; i<n; i++) { make_set(i); } //cout<<"make set success\n"; int group_num,first; for (i=0; i<m; i++) { cin>>group_num>>first; int a; for (j=1; j<group_num; j++) { cin >> a; union_set(a, first); // cout<<"union"<<a<<" "<<first<<endl; } } cout<<rank[find_set(0)]<<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