并查集初步应用,还不是很熟练。并查集两个主要函数:Union和Find。Union通常把两条不连通的支路使其连通;Find用来查找根节点,必要的要进行路径压缩。
大致题意:0号学生是默认的感染者,在M组团体中,如果出现了0号,则整个团体都是感染者。
样例:
Sample Input
100 4 //第一行两个整数N,M,表示N个学生(已编号0~N-1),M个团体 (0 < N <= 30000,0 <= M <= 500)
2 1 2 //以下M行,第一个数是该团体的人数K 后面是K个学生的编号
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sanple Output(输出每组案例的感染者数目)
4
1
1
#include<iostream>
using namespace std; int node[],flag[];
int n,m,num; void Init(int n)//初始化
{
for(int i=;i<n;i++)
node[i]=i;
} int find(int x)//查找x的父节点
{
if(node[x]==x)//父节点是它本身
return x;
else//往上找
return node[x]=find(node[x]);
} void mix(int x,int y)//使x和y连通
{
x=find(x);
y=find(y);
node[x]=y;
} int main()
{
int i;
while((cin>>n>>m)&&n*n+m*m)
{
Init(n);
while(m--)
{
cin>>num;
for(i=;i<num;i++)
cin>>flag[i];
for(i=;i<num;i++)
mix(flag[i-],flag[i]);//把输入的各点连通
}
int c=;
for(i=;i<n;i++)
{
if(find(i)==find())//判断父节点是否与一号感染者相同
c++;
}
cout<<c<<endl;
}
return ;
}