算法練習（十二）

The Suspects

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

代碼

#include<stdio.h>int pre[1001];int find(int x) {int r=x;while(r!=pre[r])r=pre[r];  // 不斷循環求得最終根return r;
}
void join(int x,int y) {int fx=find(x),fy=find(y);if(fx==0)pre[fy]=0;else if(fy==0)pre[fx]=0;else  pre[fx]=fy;         
}
int main() {int n,m;while(scanf("%d %d",&n,&m) != EOF && (m+n) != 0) {int ans=0;int i,j;for(i=0;i<n;i++) {pre[i]=i;}for(i=0;i<m;i++) {int k,a,b;scanf("%d %d",&k,&b);for(j=1;j<k;j++) {scanf("%d",&a);join(a,b);} }for(i=0;i<n;i++)if(find(i) == 0)ans++;printf("%d\n",ans);}return 0;
}

抱歉，最近有點懶了，老是拖更