poj1611（简答并查集）

题意是找出可能携带病毒的人数就是把有交集的集合合并在一起答案就是最后0所在集合的人数

并查集的一个主要思想就是合并两个不相交集合在这个题中也就是不含重复元素比如第一个集合中的1,2 就是把1， 2合并起来作为一个集合同时把num【】更新一下就是集合中的元素个数把每个集合中的第一个数作为根节点这样集合里的所有元素的祖先就是第一个数x

如果两个集合没有交集比如1,2和10 11 12 13 14 15 这两个集合就不会合并因为只是集合中的元素合并 1和2合并 10和其它的4个数合并但是要是有交集1,2和0,1 这两个集合就会合并 1，2合并了 0，1合并了那就相当于0,1,2合并了所以最后找出0所在集合的祖先节点x num[x]就是最终答案

View Code

 1 #include <stdio.h>
 2 int num[30001],father[30001],deep[30001];
 3 void init(int m)//初始化 不多说了 
 4 {
 5     int i;
 6     for(i = 0 ; i < m ; i++)
 7     {
 8         father[i] = i;
 9         num[i] = 1;
10         deep[i] = 0;
11     }
12 }
13 int find(int x)//并查集的查找 不多说
14 {
15     if(x!=father[x])
16     x = find(father[x]);
17     return father[x];
18 }
19 int union1(int x, int y)//合并 要是不懂去搜一下并查集的内容
20 {
21     x = find(x);
22     y = find(y);
23     if(x == y)
24     return;
25     if(deep[x]>=deep[y])//优化 将小的合并到大的上面
26     {
27         father[y] = x;
28         if(deep[x] == deep[y])
29         deep[x]++;
30         num[x] += num[y];
31     }
32     else
33     {
34         father[x] = y;
35         num[y]+=num[x];
36     }
37 }
38 int main()
39 {
40     int x, y, m, n, k,g;
41     while(scanf("%d%d", &m,&n)!=EOF)
42     {
43         if(m == 0&& n == 0)
44         break;
45         init(m);
46         g = n;
47         while(n--)
48         {
49             scanf("%d", &k);
50             scanf("%d",  &x);
51             k--;
52             while(k--)
53             {
54                 scanf("%d", &y);
55                 union1(x, y);
56             }
57         }
58         if(g == 0)
59         printf("1\n");
60         else
61         printf("%d\n", num[find(0)]);//找出0所在集合的祖先节点 
62     }
63     return 0;
64 }