首页 > 其他 > 详细

hdu 1232畅通工程 并查集(入门题)

时间:2014-03-02 16:47:38      阅读:528      评论:0      收藏:0      [点我收藏+]

并查集水题。。先来点并查集基础。。查找函数:

int find(int i)
{
   int t=i;
   while(bin[t]!=t)
        t=bin[t];
   return t;
}       没有路径压缩
 
 
int find(int i)
{
    int k,t;
     t=i;
    while(t!=bin[t])         
         t=bin[t];
    while(i!=t)         //修改路径---压缩
     {
         k=bin[i];
         bin[i]=t;
         i=k;
     }
     return i;

 }      带有路径压缩

还有一个递归路径压缩查找:

int find(int x)
{
 return father[x]-x ? father[x]=find(father[x]) : x;
}

分析:把已连通的公路通过并查集算法合并到一个集合。。然后通过查找有多少个不同的集合就能知道还有多少条路需要建设。。

本题代码:

bubuko.com,布布扣
#include<iostream>
using namespace std;
int father[1001];
int find(int x)
{
    return father[x]-x ? father[x]=find(father[x]) : x;
}
void unio(int x, int y)
{
    if(find(x)-find(y))    father[find(x)]=find(y);
}
int main()
{
    int n, m, i, x, y, sum;
    while(scanf("%d",&n) && n)
    {
        for(i=1; i<=n; i++)
        {
            father[i]=i;
        }
        scanf("%d",&m);
        for(i=1; i<=m; i++)
        {
            scanf("%d%d",&x,&y);
            unio(x, y);
        }
        for(sum=-1,i=1; i<=n; i++)
        {
            if(father[i]==i)    sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}
bubuko.com,布布扣

hdu 1232畅通工程 并查集(入门题),布布扣,bubuko.com

hdu 1232畅通工程 并查集(入门题)

原文:http://www.cnblogs.com/xtaq/p/3575525.html

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