首页 > 其他 > 详细

HDU 1856 More is better (并查集)

时间:2015-01-17 11:15:40      阅读:108      评论:0      收藏:0      [点我收藏+]

题目连接:请戳这里。

题目大意及思路:就是找学生最多的那个集合。注意一点的是“or there is only one boy left.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 10000000+10
using namespace std;

int f[N],num[N];
void Init(int n)
{
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        num[i]=1;
    }
}
int Find(int x)
{
    return f[x]==x?x:f[x]=Find(f[x]);
}
void Merge(int a,int b)
{
    int ra=Find(a),rb=Find(b);
    if(ra==rb) return ;
    else {
        f[rb]=ra;
        num[ra]+=num[rb];
    }
}
int main()
{
    int m;
    while(scanf("%d",&m)==1)
    {
        Init(N);
        int n=0;
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            n=max(n,max(a,b));
            Merge(a,b);
        }
        int Max=1;  //当n=0时,答案应该是1~
        for(int i=1;i<=n;i++)
            Max=max(Max,num[i]);
        printf("%d\n",Max);
    }
    return 0;
}




HDU 1856 More is better (并查集)

原文:http://blog.csdn.net/darwin_/article/details/42803709

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!