文档章节

hdu1232畅通工程 并查集

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:34
字数 656
阅读 10
收藏 0

题目链接

并查集入门题。

数组结构code1:

#include<iostream>
#define maxn 1005
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
int set[maxn];
int ifhas[maxn];
int s,e;
int n,m;
void init()
{
    int i,j;
    for(i = 1;i <= n;i ++){
        set[i] = i;
        ifhas[i] = 0;
    }
}
void Merge(int a,int b)
{
    int big,small;
    big = max(set[a],set[b]);
    small= min(set[a],set[b]);
    for(int i = 1;i <= n;i ++)
    {
        if(set[i] == big){
            set[i] = small;
        }
    }
}
int main(void)
{
    while(cin >> n && n!=0)
    {
        init();
        cin >> m;
        int i,j;
        for(i = 0;i < m;i ++){
            cin >> s >> e;
            Merge(s,e);
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(ifhas[set[i]] == 0){
                ans ++;
                ifhas[set[i]] = 1;
            }
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

 树结构code2

#include <iostream>
#include <algorithm>
#define maxn 1005
using namespace std;
int set[maxn];void init(int n)
{
    int i;
    for(i = 1;i <=n;i ++)
    {
        set[i] = i;
    }
}
int find(int x)
{
    int fa = x;
    while(fa != set[fa])
        fa = set[fa];
    return fa;
}
void merge(int a,int b)
{
    int fa,fb;
    fa = find(a);
    fb = find(b);
    set[fb] = fa;
}
int main()
{
    int n,m,a,b;
    
    while(cin >> n && n!= 0)
    {
        init(n);
        cin >> m;
        for(int i = 1;i <= m;i ++){
            cin >> a >> b;
            merge(a,b);
        }
        for(int i = 1;i <= n;i ++){
            set[i] = find(i);
            //cout << "set[" << i << "]=" << set[i] << endl;
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(set[i] == i){
                ans ++;
            }
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

树结构(优化,深度小的移到深度大的)

#include <iostream>
#include <algorithm>
#define maxn 1005
using namespace std;
int set[maxn];
int height[maxn];
void init(int n)
{
    int i;
    for(i = 1;i <=n;i ++)
    {
        set[i] = i;
        height[i] = 1;
    }
}
int find(int x)
{
    int fa = x;
    while(fa != set[fa])
        fa = set[fa];
    return fa;
}
void merge(int a,int b)
{
    int fa,fb;
    fa = find(a);
    fb = find(b);
    if(height[fa] > height[fb]){
        set[fb] = fa;
    }
    else if(height[fb] > height[fa]){
        set[fa] = fb;
    }
    else{
        set[fb] = fa;
        height[fa] ++;
    }
}
int main()
{
    int n,m,a,b;
    
    while(cin >> n && n!= 0)
    {
        init(n);
        cin >> m;
        for(int i = 1;i <= m;i ++){
            cin >> a >> b;
            merge(a,b);
        }
        for(int i = 1;i <= n;i ++){
            set[i] = find(i);
            //cout << "set[" << i << "]=" << set[i] << endl;
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(set[i] == i){
                ans ++;
            }
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

树结构(优化,深度小的移到深度大的 + 路径压缩)

#include <iostream>
#include <algorithm>
#define maxn 1005
using namespace std;
int set[maxn];
int height[maxn];
void init(int n)
{
    int i;
    for(i = 1;i <=n;i ++)
    {
        set[i] = i;
        height[i] = 1;
    }
}
int find(int x)
{
    int fa = x;
    int j,i;
    while(fa != set[fa])
        fa = set[fa];
    i = x;
    while(i != fa)
    {
        j = set[i];
        set[j] = fa;
        i = j;
    }
    return fa;
}
void merge(int a,int b)
{
    int fa,fb;
    fa = find(a);
    fb = find(b);
    if(height[fa] > height[fb]){
        set[fb] = fa;
    }
    else if(height[fb] > height[fa]){
        set[fa] = fb;
    }
    else{
        set[fb] = fa;
        height[fa] ++;
    }
}
int main()
{
    int n,m,a,b;
    
    while(cin >> n && n!= 0)
    {
        init(n);
        cin >> m;
        for(int i = 1;i <= m;i ++){
            cin >> a >> b;
            merge(a,b);
        }
        for(int i = 1;i <= n;i ++){
            set[i] = find(i);
            //cout << "set[" << i << "]=" << set[i] << endl;
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(set[i] == i){
                ans ++;
            }
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5341582.html

YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
并查集入门(hdu1232“畅通工程”)

在学习并查集之前,首先需要明白基本的并查集可以完成的功能。并查集主要是用于处理不相交集合的合并问题。它是一种基础算法,在离散数学中,可以利用并查集求一个图的连通分支,利用其这个特...

算法白菜
08/03
0
0
hdu-1979-继续畅通工程

原文链接:hdu-1979-继续畅通工程 原文: 继续畅通工程 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 26600 Accepted Submiss......

Big_laoshu
2017/11/20
0
0
并查集介绍详情

并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。 首先在地图上给你若干个城镇,这...

dingyihui2016的博客
2017/12/21
0
0
【畅通工程 HDU - 1232 】【并查集模板题】

并查集讲解和模板 有一个博文对此分析的很透彻,附链接 为避免原链接失效,现摘录如下: 为了解释并查集的原理,我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠,有上千个之多。他...

AJudge
08/22
0
0
【还是畅通工程 HDU - 1233】【Kruskal模板题】

Kruskal算法讲解 该部分内容全部摘录自刘汝佳的《算法竞赛入门经典》 Kruskal算法的第一步是给所有边按照从小到大的顺序排列。 这一步可以直接使用库函数 qsort或者sort。 接下来从小到大依次...

AJudge
08/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java读取Excel 2007

可以先读一下 【Excel 2007 底层实现方式】 1. 依赖的jar包 <dependencies> <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi</artifa......

时刻在奔跑
22分钟前
3
0
谷歌助手

https://www.lanzous.com/GoogleDownUrl

chenhongjiang
27分钟前
3
0
Makefile中.PHONY的作用是什么?

.PHONY在Makefile中是什么意思? 我已经经历过了 ,但是它太复杂了。 有人可以简单地向我解释吗? #1楼 .PHONY: install 表示“安装”一词在此Makefile中不代表文件名; 表示Makefile与同一...

技术盛宴
28分钟前
2
0
vmware 共享文件夹不显示文件的问题

安装vmtools后还是不显示执行以下操作//但是只有root权限才行 1:输入命令 sudo apt install open-vm-tools 安装工具 2:输入命令 sudo vmhgfs-fuse .host:/ /mnt/hgfs 完成设置 去除root,编...

漫步海边小路
34分钟前
3
0
mysql对子查询的优化改写

《高性能mysql第三版》提到mysql会将in子查询改写成exists查询(书中基于的mysql版本是5.1.50和5.5) 但是在5.6之后,已经优化成使用半连接查询 SELECT class_num, class_name FROM class WH...

os_m
36分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部