POJ 1611 -- The Suspects (并查集)

53 阅读 0 评论 35 点赞

我是靠谱客的博主酷炫保温杯，最近开发中收集的这篇文章主要介绍POJ 1611 -- The Suspects (并查集)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

在一所大学里有n（0 < n <= 30000）个人，并有m（0 <= m <= 500）个团体组织组织人数不等。这n个人从0 ~ n-1 编号，其中0号是感染SARS的嫌疑者，被判定为有嫌疑的机制是与嫌疑者在同一组织内。问共有多少嫌疑者？

思路

运用并查集的方法，合并与查找，在输入的过程中把一个个分开的集合合并成一个个大的集合，最后查找0号。

合并：构造数组，为n个学生的各自的集合，合并的过程中集合与集合之间形成一棵棵的树，每个节点的根节点是各自的上一层的节点，树的根节点是它本身。

查找：从当前节点一层层向上查找根节点的过程。

code

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

int pre[50005];
int num[50005];

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        pre[i]=i;
        num[i]=1;
    }
}

int Find(int x)
{
    int r=x;

    while(pre[r]!=r)
        r=pre[r];
/*
    int i=x,j;  //有无压缩路径的情况

    while(i!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
*/
    return r;
}

void join(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);

    if(fx!=fy)
    {
        pre[fx]=fy;
        num[fy]+=num[fx];
    }
}

int main()
{
    int n,m,k,x,y;

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0 && m==0)
            break;

        init(n);

        for(int i=0;i<m;i++)
        {
            scanf("%d",&k);
            scanf("%d",&x);

            for(int i=1;i<k;i++)
            {
                scanf("%d",&y);
                join(x,y);
                x=y;
            }
        }


        int p=Find(0);
        printf("%dn",num[p]);

        for(int i=0;i<n;i++)
            printf("%d ",pre[i]);
    }
    return 0;
}
/*无压缩路径*/
/*
100 4
2 1 2
5 1 10 13 11 14
2 0 1
2 99 2
8
14 2 10 3 4 5 6 7 8 9 13 14 12 11 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 14
*/
/*有压缩路径*/
/*
100 4
2 1 2
5 1 10 13 11 14
2 0 1
2 99 2
8
14 14 14 3 4 5 6 7 8 9 14 14 12 14 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 14
*/

不可不看这篇博客，很有意思。

https://blog.csdn.net/u013546077/article/details/64509038