1宫患、題意##
為了防止SARA傳播刊懈,NSYSU收集所有學(xué)生組的成員列表,一旦群組中的成員是可疑人員娃闲,群組中的所有成員都是可疑人員虚汛。當(dāng)學(xué)生被認(rèn)定為患病嫌疑時(shí),識(shí)別所有有嫌疑的學(xué)生并不容易皇帮。你的工作是寫(xiě)一個(gè)程序卷哩,找到所有的有嫌疑的學(xué)生。
也就是用并查集將每一組的同學(xué)連起來(lái)属拾,一旦組內(nèi)有一個(gè)人有嫌疑将谊,直接排除ta所在的那組冷溶。
2、輸入數(shù)據(jù)分析
100 4 //第一組樣例尊浓,總數(shù)n = 100人逞频, m = 4個(gè)小組
2 1 2 //第一個(gè)數(shù)據(jù)k代表小組總不能人數(shù),后面數(shù)據(jù)是小組組員的號(hào)數(shù)
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號(hào)默認(rèn)為感染者
0 0 //n, m為0苗胀,結(jié)束輸入
3、輸出數(shù)據(jù)分析
4 //第1褒颈、3柒巫、4小組為感染者組,共4人
1
1
4谷丸、代碼樣例
#include <stdio.h>
int pre[50005]; //父節(jié)點(diǎn)數(shù)組
int lw[50005];
int i, j;
void ini(int n) //預(yù)處理
{
for(i = 0; i < n; i++)
{
pre[i]=i;
lw[i]=1;//可用memset(lw, 0, sizeof(lw))放在for循環(huán)之前;
}
}
int Find(int x) //查找根節(jié)點(diǎn)
{
if(x!=pre[x])
pre[x] = Find(pre[x]);
return pre[x];
}
void uoin(int x,int y)//合并
{
int xx = Find(x);
int yy = Find(y);
if(xx != yy)
{
pre[xx] = yy;
lw[yy] += lw[xx];
}
}
int main()
{
int n, m, t, x, y, res;
while(scanf("%d%d", &n, &m) != EOF)
{
if(n==0 && m==0) break;//n,m都為0堡掏,直接結(jié)束程序
ini(n);
for(i = 0; i < m; i++)
{
scanf("%d", &t);
scanf("%d", &x);//輸入小組第一號(hào)成員
for(j = 1; j < t; j++)
{
scanf("%d", &y);//輸入小組剩余成員
uoin(x, y);//每輸入一個(gè)和上一個(gè)連在一起
x = y;
}
}
res = Find(0);//看有沒(méi)有0節(jié)點(diǎn),如果有查找誰(shuí)與0號(hào)連在一起
printf("%d\n", lw[res]);//取個(gè)巧輸出
}
return 0;
}
PS. 這題不能用#include<bits/stdc++.h>會(huì)挖