并查集（Union-Find）

水深无声 2021-12-20 06:29 212阅读 0赞

### Date：2019-06-23 13:42:53 ###

1 //定义
     2 int father[N];  //father[1]=2,即2是1的父亲，根结点用father[i]=i表示
     3 
     4 //初始化
     5 for(int i=1; i<=N; i++)
     6     father[i]=i;    //初始时有N个独立的集合
     7 
     8 //查找
     9 //对于给定的结点，寻找其根结点
    10 int Find(int x)
    11 {
    12     if(father[x] == x)
    13         return x;
    14     Find(father[x]);
    15 }
    16 
    17 //合并
    18 void Union(int a, int b)
    19 {
    20     int fa = Find(a);
    21     int fb = Find(b);
    22     father[fb] = fa;    //不能用father[a]=b
    23     Find2(b);          //将fb中的结点更新至fa
    24 }
    25 
    26 
    27 //路径压缩
    28 //把当前查询结点的路径上所有的结点的父亲都指向根结点
    29 int Find2(int x)
    30 {
    31     int r = x;
    32     while(x != father[x])
    33         x = father[x];
    34     //此处x已经是根结点
    35     while(r != father[r])
    36     {
    37         int z = r;
    38         r = father[r];
    39         father[z] = x;
    40     }
    41 }
    42 
    43 //递归写法
    44 int Find2(int x)
    45 {
    46     if(x == father[x])
    47         return x;
    48     fathre[x] = Find2(father[x]);
    49 }

转载于:https://www.cnblogs.com/blue-lin/p/11072511.html

发表评论取消回复

表情：

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

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

相关阅读

相关并查集 Ⅱ

\[poj 1611\] ([http://poj.org/problem?id=1611][http_poj.org_problem_id_1611]) 题目描述： T

古城微笑少年丶/ 2022年08月03日 14:35/ 0 赞/ 281 阅读

相关并查集

并查集JAVA版框架并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组

落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 316 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 301 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 308 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 367 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 373 阅读

相关并查集

> 并查集是一种树形的数据结构，用于集合的合并。与C++STL相比的优势： 1. 可以同时维护多个集合 2. 快速的合并两个集合 \\现实：用数组实现。fat

左手的ㄟ右手/ 2022年02月05日 00:23/ 0 赞/ 262 阅读

相关并查集

例题： ![输入样例][20190805122001677.png] 输入样例，第一行为一个整数n，代表有n台电脑，编号1-n；接下来进行一系列操作，当输入‘c’时，判

Dear 丶/ 2021年11月11日 08:04/ 0 赞/ 388 阅读

相关并查集

一、算法解释用于解决一些有N个元素的集合应用问题。 1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。 ![这里写图片描述][S

桃扇骨/ 2021年09月14日 02:56/ 0 赞/ 476 阅读

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 573 阅读