文章作者：ktyanny?文章來源：ktyanny?轉(zhuǎn)載請(qǐng)注明，謝謝合作。?

ktyanny：a的第一道并查集。

題目描述：

有很多組學(xué)生，在同一個(gè)組的學(xué)生經(jīng)常會(huì)接觸，也會(huì)有新的同學(xué)的加入。但是SARS是很容易傳染的，只要在改組有一位同學(xué)感染SARS，那么該組的所有同學(xué)都被認(rèn)為得了SARS。現(xiàn)在的任務(wù)是計(jì)算出有多少位學(xué)生感染SARS了。假定編號(hào)為0的同學(xué)是得了SARS的。

解題思路---->顯然并查集了。并查集的詳細(xì)解釋在可以點(diǎn)擊?并查集（不相交集合）進(jìn)行學(xué)習(xí)。采用num[]存儲(chǔ)該集合中元素個(gè)數(shù)，并在集合合并時(shí)更新num[]即可。然后找出0所在的集合的根節(jié)點(diǎn)x，因此，num[x]就是answer了。

?

ac代碼： 16MS C++

?

#include?<stdio.h>//by ktyanny
#include?<iostream>
using?namespace?std;

const?int?MAXN?=?30001;?/*結(jié)點(diǎn)數(shù)目上線*/
int?pa[MAXN];????/*p[x]表示x的父節(jié)點(diǎn)*/
int?rank[MAXN];????/*rank[x]是x的高度的一個(gè)上界*/
int?num[MAXN];/*num[]存儲(chǔ)該集合中元素個(gè)數(shù)，并在集合合并時(shí)更新num[]即可*/

void?make_set(int?x)
{/*創(chuàng)建一個(gè)單元集*/
????pa[x]?=?x;
????rank[x]?=?0;
????num[x]?=?1;
}

int?find_set(int?x)
{/*帶路徑壓縮的查找*/
????/*保存待查找的數(shù)*/
????int?r?=?x,?temp;
????/*找到根節(jié)點(diǎn)*/
????while(pa[r]?!=?r)?r?=?pa[r];
????while(x?!=?r)
????{
????????temp?=?pa[x];
????????pa[x]?=?r;
????????x?=?temp;
????}
????return?x;
????//if(x?!=?pa[x]) //注釋掉的其實(shí)也是可以的，不過不想用遞歸來做啦
????//????pa[x]?=?find_set(pa[x]);
????//return?pa[x];
}

/*按秩合并x，y所在的集合*/
void?union_set(int?x,?int?y)
{
????x?=?find_set(x);
????y?=?find_set(y);
????if(x?==?y)return?;
????if(rank[x]?>?rank[y])/*讓rank比較高的作為父結(jié)點(diǎn)*/
????{
????????pa[y]?=?x;
????????num[x]?+=?num[y];
????}
????else?
????{
????????pa[x]?=?y;
????????if(rank[x]?==?rank[y])
????????????rank[y]++;
????????num[y]?+=?num[x];
????}
}

//answer?to?1611?
int?main()
{
????int?n,?m,?x,?y,?i,?t,?j;
????while(scanf("%d%d",?&n,?&m))
????{
????????if(m==n?&&?n?==?0)?break;
????????if(m?==?0)
????????{
????????????cout?<<?"1\n";?continue;
????????}
????????for(i?=?0;?i?<?n;?i++)
????????????make_set(i);
????????for(i?=?0;?i?<?m;?i++)
????????{
????????????scanf("%d",?&t);
????????????scanf("%d",?&x);
????????????for(j?=?1;?j?<?t;?j++){
????????????????scanf("%d",?&y);
????????????????union_set(x,?y);
????????????????x?=?y;
????????????}
????????}
????????x?=?find_set(0);/*找到0所在的樹的樹根*/
????????//int?ans?=?0;
????????//for(i?=?0;?i?<?n;?i++)
????????//????if(pa[i]?==?x)
????????//????????ans++;
????????//cout?<<?ans?<<?endl;
????????cout?<<?num[x]?<<?endl;
????}
????return?0;
}

?

?測(cè)試數(shù)據(jù)：

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?

轉(zhuǎn)載于:https://www.cnblogs.com/ktyanny/archive/2009/12/09/1620304.html

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的POJ 1611 The Suspects （并查集）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。