即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

POJ 1611 (并查集)

编程语言 Since_natural_ran 12℃ 0评论

题意:

有n个学生,编号0~n-1,现在有m个由学生组成的群体,群体里面有一个感染病的话


都感染,0是最初的感染源。

思路:

最开始以为直接Find()就行了,把每一个群体的第一个人当作father,但是发现这


样会重合,使得被0感染的并且在其它群体的人找不到,后来发现直接按照群体来合并


这样最后直接找0在哪一个群体就行了。

/*
#include 
#include 
#include 

using namespace std;

const int MAXN = 30005;

int n,m;
int f[MAXN];
//int sus[505][100];


int Find(int x)
{
    return x == f[x] ? x : (f[x] = Find(f[x]));
}

int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m) != EOF) {
        if(n == 0 && m == 0)
            break;
        for(int i = 0;i < n; i++)
            f[i] = i;
        for(int i = 0;i < m; i++) {
            int temp;
            int k;
            scanf("%d",&k);
            int fa;
            int flag = false;
            for(int j = 0;j < k; j++) {
                scanf("%d",&temp);
                int a = Find(temp);
                if(j == 0)
                    fa = a;
                if(temp == 0)
                    flag = true;
                f[temp] = fa;
            }
            if(flag)
                f[fa] = 0;
        }
        int ans = 0;
        for(int i = 0;i < n; i++) {
            int b = Find(i);
            if(b == 0)
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}
*/
#include 
#include 
#include 

using namespace std;

const int MAXN = 30005;

int n,m,k,fa;
int f[MAXN];
int num[MAXN];

int Find(int x)
{
    return x == f[x] ? x:f[x] = Find(f[x]);
}

void union_find(int x,int y)
{
    int a = Find(x);
    int b = Find(y);
    if(num[a] > num[b]) {
        f[b] = a;
        num[a] += num[b];
    }
    else {
        f[a] = b;
        if(num[b] > num[a])
            num[b] += num[a];
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m) != EOF) {
        if(n == 0 && m == 0)
            break;
        for(int i = 0;i < n; i++) {
            num[i] = 1;
            f[i] = i;
        }
        for(int i = 0;i < m; i++) {
            scanf("%d",&k);
            if(k >= 1)
                scanf("%d",&fa);
            for(int j = 0;j < k-1; j++) {
                int temp;
                scanf("%d",&temp);
                union_find(fa,temp);
            }
        }
        int ans = 0;
        for(int i = 0;i < n; i++) {
            if(Find(i) == Find(0))
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}























转载请注明:CodingBlog » POJ 1611 (并查集)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情