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