pku 1611 The Suspects 并查集的应用

http://poj.org/problem?id=1611

思路：统计出和0能够联系在一起的点，然后输出其个数

View Code #include <cstdio>
#include <iostream>
#define maxn 30004
using namespace std;

int f[maxn],num[maxn];//num记录与0有联系的个数
int n,m;

int find(int x)
{
if (x != f[x])
{
f[x] = find(f[x]);
}
return f[x];
}
void Union(int x,int y)
{
x = find(x);
y = find(y);
if (x != y)
{
f[y] = x;
num[x] += num[y];//根记录子系的个数
}
}
int main()
{
int i,j,a,b,k;
while (cin>>n>>m)
{
if (!n && !m) break;
for (i = 0; i <= n; ++i)
{
f[i] = i;
num[i] = 1;
}
for (i = 0; i < m; ++i)
{
cin>>k;
if (k)
cin>>a;
for (j = 1; j < k; ++j)
{

cin>>b;
Union(a,b);
}
}
int pos = find(0);//找到0所在的子系的根
printf("%d\n",num[pos]);

}
return 0;
}

转载于:https://www.cnblogs.com/E-star/archive/2012/03/23/2414292.html

总结

以上是生活随笔为你收集整理的pku 1611 The Suspects 并查集的应用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。