| ||||||||||
| 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 | |||||||||
Re:第一个并查集,留念In Reply To:第一个并查集,留念 Posted by:fzhang at 2011-12-20 13:32:31 #include <iostream>
using namespace std;
#define MAXN 30000
int father[MAXN],rank[MAXN];
void Init(int n)
{
int i;
for(i=0; i<n; i++)
{
father[i]=i;
rank[i]=1;
}
}
int Find_Set(int x)
{
if(x!=father[x])
{
father[x]=Find_Set(father[x]);
}
return father[x];
}
void Union(int x,int y)
{
x=Find_Set(x);
y=Find_Set(y);
// if(x==y)return;
if(x!=y)
{
if(rank[x]>=rank[y])
{
father[y]=x;
rank[x]=rank[x]+rank[y];
}
else
{
father[x]=y;
rank[y]=rank[y]+rank[x];
}
}
}
int main()
{
int n,m,k,first,next;
int i,j;
while(cin>>n>>m)
{
if(n==0 && m==0)break;
Init(n);
for(i=0; i<m; i++)
{
cin>>k>>first;
for(j=1; j<k; j++)
{
cin>>next;
Union(first,next);
}
}
cout<<rank[father[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