并查集初步应用,还不是很熟练。并查集两个主要函数: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 ;
}
05-11 02:53