| ||||||||||
| 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 | |||||||||
= =In Reply To:苍天呐!!为毛一直wa!!!! Posted by:ylqfp at 2011-06-26 11:09:34 直接在提交框里改的代码,没有缩进,抱歉>__<
#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; if (!group_num) continue;
cin>>first;
int a;
for (j=1; j<group_num; j++)
{
cin >> a;
union_set(a, first);
// cout<<"union"<<a<<" "<<first<<endl;
}
}
int px=find_set(0);
int ans=0; for (i=0; i<n; i++) if (find_set(i)==px) ans++;
cout<<ans<<"\n";
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator