1 /*
2 题意：id是0的是感染者，和他在同一组的会被感染，问最后被感染的人数
3 并查集：算是入门题吧，考察按秩合并，也就是rk[x]记录x的子节点有多少个，不管往哪合并，最后只要求0在的树上的所有节点就行了
4 */
5 /************************************************
6 * Author :Running_Time
7 * Created Time :2015-8-10 9:40:32
8 * File Name :POJ_1611.cpp
9 ************************************************/
10
11 #include <cstdio>
12 #include <algorithm>
13 #include <iostream>
14 #include <sstream>
15 #include <cstring>
16 #include <cmath>
17 #include <string>
18 #include <vector>
19 #include <queue>
20 #include <deque>
21 #include <stack>
22 #include <list>
23 #include <map>
24 #include <set>
25 #include <bitset>
26 #include <cstdlib>
27 #include <ctime>
28 using namespace std;
29
30 #define lson l, mid, rt << 1
31 #define rson mid + 1, r, rt << 1 | 1
32 typedef long long ll;
33 const int MAXN = 3e4 + 10;
34 const int INF = 0x3f3f3f3f;
35 const int MOD = 1e9 + 7;
36 struct UF {
37 int rt[MAXN], rk[MAXN];
38 void init(void) {
39 memset (rt, -1, sizeof (rt));
40 memset (rk, 0, sizeof (rk));
41 }
42 int Find(int x) {
43 return rt[x] == -1 ? x : rt[x] = Find (rt[x]);
44 }
45 void Union(int x, int y) {
46 x = Find (x); y = Find (y);
47 if (x == y) return ;
48 if (rk[x] >= rk[y]) {
49 rt[y] = x; rk[x] += rk[y] + 1;
50 }
51 else {
52 rt[x] = y; rk[y] += rk[x] + 1;
53 }
54 }
55 bool same(int x, int y) {
56 return Find (x) == Find (y);
57 }
58 }uf;
59 int n, m;
60
61 int main(void) { //POJ 1611 The Suspects
62 while (scanf ("%d%d", &n, &m) == 2) {
63 if (!n && !m) break;
64 uf.init ();
65 for (int i=1; i<=m; ++i) {
66 int k, f; scanf ("%d", &k);
67 for (int i=1; i<=k; ++i) {
68 int x; scanf ("%d", &x);
69 if (i == 1) {
70 f = x; continue;
71 }
72 uf.Union (f, x);
73 }
74 }
75
76 printf ("%d
", uf.rk[uf.Find (0)] + 1);
77 }
78
79 return 0;
80 }
并查集 POJ 1611 The Suspects
编译人生，运行世界！