题目链接:
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66964#problem/B
题目描述:
有n个社团,每个人可以参加多个,其中有一个人代号为0,认为与0在一个社团的其他成员也都感染了病毒,从而认为,在一个社团里面如果有人感染了病毒,则这个社团里的所有人都感染,求一共多少人感染病毒
输入:
有多组数据,m,n都为0时结束
第一行n, m表示有n个人m个社团
之后m行,第一个数字表示当前社团人数 之后输入人员编号;
输出:
每组数据输出一行,表示感染人数
思路:
并查集,当合并时更新当前父亲节点的儿子个数
最后结果为编号为0的人的父亲节点的儿子个数
初始化每个节点儿子为1,父亲是自己
代码:
/*************************************************************************
> File Name: poj_1611.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年03月28日 星期一 13时38分31秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 50086;
int p[N];
int ans = 1;
int son[N];
int find(int x) { return x == p[x]? x : p[x] = find(p[x]); }
void init(int n)
{
for(int i = 0; i < n; i++)
{
p[i] = i;
son[i] = 1;
}
}
void inside(int x, int y)
{
x = find(x);
y = find(y);
if(x != y)
{
p[y] = x;
son[x] += son[y];
}
}
int main()
{
int n, m;
while(scanf("%d%d", &n, &m) && n+m)
{
init(n);
ans = 1;
int p = -1;
for(int i = 0; i < m; i++)
{
int k, t, x;
scanf("%d", &k);
scanf("%d", &t);
for(int j = 1; j < k; j++)
{
scanf("%d", &x);
inside(t, x);
//t = x;
}
}
printf("%d\n", son[find(0)]);
}
return 0;
}