| ||||||||||
| 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