題意：
? ? ? 有一個(gè)人生病了，和他一個(gè)社團(tuán)或者間接和他有聯(lián)系的人都會(huì)生病，問一共有多少人生病了。


思路：
? ? ? 比較簡單和基礎(chǔ)的題，帶權(quán)并查集中的一種，就是記錄更新集合元素個(gè)數(shù)，這個(gè)題目我是開始的時(shí)候每個(gè)人自己在自己的集合里，元素個(gè)數(shù)是1，然后在多開出來m個(gè)集合，讓第i個(gè)社團(tuán)直接映射到i+n個(gè)集合，元素個(gè)數(shù)一開始是0，然后就是簡單更新了，還有就是注意下兩個(gè)人已經(jīng)屬于同一個(gè)集合的時(shí)候就直接跳過，不用處理。


#include<stdio.h>
#include<string.h>


#define N 30000 + 500 + 10


int mer[N] ,sum[N];


int finds(int x)
{
? ? return x == mer[x] ? x : mer[x] = finds(mer[x]);
}


int main ()
{
? ? int n ,m ,i ,a ,k;
? ? while(~scanf("%d %d" ,&n ,&m) && n + m)
? ? {
? ? ? ? for(i = 1 ;i <= n + m ;i ++)
? ? ? ? {
? ? ? ? ? ? if(i <= n) sum[i] = 1;
? ? ? ? ? ? else sum[i] = 0;
? ? ? ? ? ? mer[i] = i;
? ? ? ? }
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&k);
? ? ? ? ? ? int y = finds(i+n);
? ? ? ? ? ? while(k--)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? scanf("%d" ,&a);
? ? ? ? ? ? ? ? ++a;
? ? ? ? ? ? ? ? int x = finds(a);
? ? ? ? ? ? ? ? if(x == y) continue;
? ? ? ? ? ? ? ? mer[x] = y;
? ? ? ? ? ? ? ? sum[y] += sum[x];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int x = finds(1);
? ? ? ? printf("%d\n" ,sum[x]);
? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ1611基础带权并查集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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