POJ1611基础带权并查集

题意：

有一个人生病了，和他一个社团或者间接和他有联系的人都会生病，问一共有多少人生病了。

思路：

比较简单和基础的题，带权并查集中的一种，就是记录更新集合元素个数，这个题目我是开始的时候每个人自己在自己的集合里，元素个数是1，然后在多开出来m个集合，让第i个社团直接映射到i+n个集合，元素个数一开始是0，然后就是简单更新了，还有就是注意下两个人已经属于同一个集合的时候就直接跳过，不用处理。

#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;

}

巴特西

POJ1611基础带权并查集

最新文章

热门文章