POJ 1611 The Suspects （并查集）

The Suspects

題目鏈接：

http://acm.hust.edu.cn/vjudge/contest/123393#problem/B

Description

嚴重急性呼吸系統綜合癥( SARS), 一種原因不明的非典型性肺炎,從2003年3月中旬開始被認為是全球威脅。為了減少傳播給別人的機會, 最好的策略是隔離可能的患者。
在Not-Spreading-Your-Sickness大學( NSYSU), 有許多學生團體。同一組的學生經常彼此相通,一個學生可以同時加入幾個小組。為了防止非典的傳播,NSYSU收集了所有學生團體的成員名單。他們的標準操作程序(SOP)如下：
一旦一組中有一個可能的患者, 組內的所有成員就都是可能的患者。
然而,他們發現當一個學生被確認為可能的患者后不容易識別所有可能的患者。你的工作是編寫一個程序, 發現所有可能的患者。

Input

輸入文件包含多組數據。
對于每組測試數據：
第一行為兩個整數n和m, 其中n是學生的數量, m是團體的數量。0 < n <= 30000，0 <= m <= 500。
每個學生編號是一個0到n-1之間的整數，一開始只有0號學生被視為可能的患者。
緊隨其后的是團體的成員列表，每組一行。
每一行有一個整數k，代表成員數量。之后,有k個整數代表這個群體的學生。一行中的所有整數由至少一個空格隔開。
n = m = 0表示輸入結束，不需要處理。

Output

對于每組測試數據, 輸出一行可能的患者。

Sample Input

100 4
2 1 2
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

Sample Output

4
1
1

題意：

有n個學生，分成m個小組;
若有學生可能感染SARS，則其所在的小組均被視為可能的患者.
一開始只有學生#0染病;
輸出所有可能的患者的數量.

題解：

很明顯的并查集模版題.
將同一小組的所有人合并到一起;
查詢每個學生是否跟#0在一個集合.

代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define LL long long
#define eps 1e-8
#define maxn 31000
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;int fa[maxn];
int rank[maxn];void init_set() {for(int i=0; i<maxn; i++) {fa[i] = i;rank[i] = 0;}
}int find_set(int x) {return fa[x] = (x==fa[x]? x:find_set(fa[x]));
}void unit_set(int x, int y) {x = find_set(x);y = find_set(y);if(rank[x] < rank[y]) swap(x, y);fa[y] = x;if(rank[x] == rank[y]) rank[x]++;
}int n, m;int main(int argc, char const *argv[])
{//IN;while(scanf("%d %d", &n,&m) != EOF && (m||n)){init_set();while(m--) {int k; scanf("%d", &k);if(!k) continue;int x; scanf("%d", &x); k--;while(k--) {int y; scanf("%d", &y);unit_set(x, y);}}int cnt = 0;for(int i=0; i<n; i++) {if(find_set(i) == find_set(0)) cnt++;}printf("%d\n", cnt);}return 0;
}