Yiner的ACM

成长的痕迹
<2011年2月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

统计

  • 随笔 - 29
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

并查集 HDU1232

 

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

bool flags[1001];
int father[1001];

void makeset(int n)
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
}

int findset(int x)
{
    if(x!=father[x])
    {
        father[x]=findset(father[x]);
    }
    return father[x];
}

void Union(int a,int b)
{
    int x=findset(a);
    int y=findset(b);
    if(x==y)
    return;
        father[y]=x;
}

int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(flags,false,sizeof(flags));
        if(n==0)
        break;
        makeset(n);
        int first,second;
        for(int i=1;i<=m;i++)
         {
             scanf("%d %d",&first,&second);
             Union(first,second);
         }
         for(int i=1;i<=n;i++)//判断树的棵数
         {
             flags[findset(i)]=true;
         }
         int k=0;
         for(int i=1;i<=n;i++)
         {
             if(flags[i]==true)
             k++;
         }
         printf("%d\n",k-1);//需要增加的路数等于树的棵树k-1
    }
        return 0;
}

posted on 2011-03-30 20:38 Yiner 阅读(481) 评论(0)  编辑 收藏 引用 所属分类: 并查集


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理