首页 > 其他 > 详细

HDOJ1213(并查集)

时间:2015-08-05 21:55:55      阅读:145      评论:0      收藏:0      [点我收藏+]

set容器中的值互异,非常好用。

水题,直接贴代码了

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
set<int> ans;
const int SIZE=1000+16;
int par[SIZE];
int rnk[SIZE];
void init(int n)
{
    for(int i=0; i<=n; i++)
    {
        par[i]=i;
        rnk[i]=0;
    }
}

int fnd(int x)
{
    if(par[x]==x)
        return x;
    return par[x]=fnd(par[x]);
}

void unite(int x, int y)
{
    int a=fnd(x);
    int b=fnd(y);
    
    if(a==b)
        return ;
    if(rnk[a]<rnk[b])
    {
        par[a]=b;
    }
    else
    {
        par[b]=a;
        if(rnk[a]==rnk[b])
            rnk[a]++;
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ans.clear();
        int n, m;
        scanf("%d %d",&n, &m);
        init(n);
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d %d",&x, &y);
            unite(x,y);    
        }
        
        for(int i=1;i<=n;i++)
        {
            ans.insert(fnd(i));
        }
        
        printf("%d\n",ans.size());
    }
    
    return 0;
}

 

HDOJ1213(并查集)

原文:http://www.cnblogs.com/program-ccc/p/4705802.html

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