数据结构：并查集

向右看齐 2022-05-30 05:49 136阅读 0赞

[杭电OJ：畅通工程][OJ]

#include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    
    int father[10005];
    bool arr[10005];
    
    void init () {
        for (int i=0; i<1000; i++) {
            father[i] = i;
        }
    }
    
    int find (int x) {//查找并压缩路径
        return father[x] == x ? x : father[x] = find(father[x]);
    }
    
    void join (int x, int y) {
        int p1 = find(x);
        int p2 = find(y);
    
        if (p1 == p2) {
            return;
        }
    
        father[p1] = p2;
    }
    
    bool check (int x, int y) {
        int p1 = find(x);
        int p2 = find(y);
    
        if (p1 == p2) {
            return true;
        }
        else {
            return false;
        }
    }
    
    int main (int argc, char **argv) {
        int m, n;
        int a, b;
        int ans;
        while (scanf("%d",&m)) {//m城镇,n道路
            if (m == 0) { break; }
            scanf("%d", &n);
            init();
            ans = 0;
            for (int i=1; i <= n; i++) {
                scanf("%d %d", &a, &b);
                join(a, b);
            }
            memset(arr, 0, sizeof(arr));
            for (int i=1; i <= m; i++) {
                arr[find(i)] = 1;
            }
            for (int i=1; i <= m; i++) {
                if (arr[i]) {
                    ans++;
                }
            }
            printf("%d\n", ans - 1);
        }
        return 0;
    }

[OJ]: http://acm.hdu.edu.cn/showproblem.php?pid=1232

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】并查集：Java实现并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。它支持两种操作：查找（Find）：确定某个元素处于哪个子集，或者判断某一元素是否

柔光的暖阳◎/ 2022年12月12日 04:58/ 0 赞/ 131 阅读

相关【数据结构】并查集

并查集需求引出并查集并查集（Union Find）如何存储数据？接口定义元素的初始化 UnionFind.java（abst

た入场券/ 2022年11月09日 12:52/ 0 赞/ 144 阅读

相关数据结构——并查集

`特点：` `实现简单，效率较高。` `功能：` `1，集合的快速合并；` `2，快速查找某元素所在集合。` `优化：` `1，合并优化；` `2，路径压缩。`

逃离我推掉我的手/ 2022年05月30日 06:41/ 0 赞/ 141 阅读

相关数据结构：并查集

[杭电OJ：畅通工程][OJ] include <stdio.h> include <stdlib.h> include <memory.h>

向右看齐/ 2022年05月30日 05:49/ 0 赞/ 137 阅读

相关【数据结构】并查集

　　先看一道题：假如已知有n个人和m对好友关系（存于数组r），如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们是属于同一个朋友圈，请写程序求出n个人里一共有多少个

深碍√TFBOYSˉ_/ 2022年05月27日 05:51/ 0 赞/ 147 阅读

相关数据结构------并查集

-------------------- 先来看一道题：假设一组有n个人和m对好友关系(存于数组r)。如果两个人是直接或者间接好友(好友的好友就是间接好友)，则认为他们

àì夳堔傛蜴生んèń/ 2022年05月25日 21:14/ 0 赞/ 147 阅读

相关数据结构-并查集

数据结构-并查集 -------------------- 何为并查集简述并查集(Union Find)是一种用于管理分组的数据结构。它具备

素颜马尾好姑娘i/ 2022年05月15日 03:05/ 0 赞/ 247 阅读

相关数据结构——并查集Union Find

一、并查集解决了什么问题？ 1、网络中节点间的连接状态：这里的网络是一个抽象的概念，指的是用户之间形成的网络 2、两个或两个以上集合之间的交集二、对并查集的

╰半夏微凉°/ 2022年05月14日 16:28/ 0 赞/ 202 阅读

相关数据结构之并查集

数据结构并查集的学习：并查集在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算

分手后的思念是犯贱/ 2022年01月30日 09:43/ 0 赞/ 216 阅读

相关数据结构4——并查集（入门）

一、问题引入原题：[杭电hdu1232畅通工程][hdu1232] 题意：首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最

短命女/ 2021年12月21日 14:11/ 0 赞/ 211 阅读