Week6 作业 B

题目描述：

有n个学生，m个学生群体，其中有一个编号为0的学生感染了病毒，则只要是与0号学生直接接触或传递接触的人，都是The Suspects疑似病人，问有多少个疑似病人。

思路：

并查集。输入时，可以单独输入每个学生团体的第一个人，然后让后边的人都与第一个人进行合并。

代码：

（未使用重量规则）

 1 #include <cstdio>
 2 #include <iostream> 
 3 const int MAXN=1e5+5;
 4 using namespace std;
 5 int fa[MAXN];
 6 void init(int n)
 7 {
 8     for(int i=0;i<n;i++)
 9         fa[i]=i;
10 }
11 int find(int x)
12 {
13     if(fa[x]==x) return fa[x];
14     fa[x]=find( fa[x] );
15     return fa[x];
16 }
17 void unite(int x,int y)
18 {
19     int root1=find(x),root2=find(y);
20     fa[root1]=root2;
21 }
22 int main()
23 {
24     int n,m;
25     while( scanf("%d %d",&n,&m) && !(m==0 && n==0))
26     {    
27         init(n);
28         for(int i=1;i<=m;i++)
29         {
30             
31             int num,t2,t3; scanf("%d %d",&num,&t2);
32             for(int j=2;j<=num;j++)
33             {
34                 scanf("%d",&t3);
35                 unite(t2,t3);
36             }
37         }
38         int ans=0;
39         for(int i=0;i<n;i++)
40         {
41             if( find(i)==find(0) ) ans++;
42         }
43         cout<<ans<<endl;
44     }    
45 }