題目大意是給一群人，這里面可以確定的是編號為0的人一定是有病的，已知一個(gè)小組中如果有一個(gè)人有病，那么就說明整個(gè)小組都有病，求這群人中有多少個(gè)人有病。
這道題給的小組中的元素實(shí)際上是一定屬于一個(gè)集合里面的，那么小組中每一個(gè)元素都要合并到一起，當(dāng)然，有的元素可能已經(jīng)是其它集合里面的了，不過沒關(guān)系，我們需要的只是患病團(tuán)體和不患病團(tuán)體，最終所有的人全都合并完以后，明顯患病團(tuán)體應(yīng)該是含有0號人的那個(gè)集合，那么我們只需要查找一下0集合里面存在多少個(gè)元素就可以了。
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 30010
9 struct data
10 {
11 int p, n;
12 }p[N];
13 int find(int x)
14 {
15 int temp;
16 if (x == p[x].p) return x;
17 temp = p[x].p;
18 p[x].p = find(temp);
19 return p[x].p;
20 }
21 int main()
22 {
23 int n, m, k;
24 int a[N];
25 int r1, r2;
26 while (scanf("%d%d", &n, &m) != EOF)
27 {
28 if (n == 0 && m == 0) break;
29 for (int i = 0; i < n; i++)
30 {
31 p[i].p = i;
32 p[i].n = 1;
33 }
34 for (int i = 0; i < m; i++)
35 {
36 memset(a, 0, sizeof(a));
37 scanf("%d", &k);
38 for (int j = 0; j < k; j++) scanf("%d", &a[j]);
39 for (int j = 1; j < k; j++)
40 {
41 r1 = find(a[j - 1]); r2 = find(a[j]);
42 if (r1 != r2)
43 {
44 p[r2].p = r1;
45 p[r1].n += p[r2].n;
46 }
47 }
48 }
49 int r = find(0);
50 printf("%d\n", p[r].n);
51 }
52 return 0;
53 }
54