并查集

桃扇骨 2021-09-14 02:56 451阅读 0赞

## **一、算法解释** ##

用于解决一些有N个元素的集合应用问题。  
1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。  
![这里写图片描述][SouthEast]  
2、现在我们想将3和1元素连线并成一个集合。可以将p\[3\] = 1。当p\[3\] ！= 3时说明该元素集合已经并入其他集合。  
![这里写图片描述][SouthEast 1]  
3、现在我们又将2与3连线并入一个集合，可以将p\[2\] = p\[3\]。  
![这里写图片描述][SouthEast 2]  
算法巧妙之处：一是利用集合中元素最大或最小节点编号作为集合标记，这样只要P\[i\]的值属于同一个值就表明他们属于一个集合；二是利用节点编号的大小关系形成一条链，通过这条链，我们可以搜索到当前元素所在集合标记。

## **二、代码** ##

// 递归搜索当前节点所在子最小生成树标记。并在搜索过程中将同一子集的各节点标记置位该子集中最小节点号。
    int find(int node){
        if(flag[node]==node) return node;
        else return flag[node] = find(flag[node]);
    }
    for(int j=0; j<m; j++){
            // 搜索u，v节点所属子最小生成树标记
            int x = find(edges[j].u);
            int y = find(edges[j].v);
            // 将路径中两个点归于同一子集，因为我们将同一子集中的最小节点号作为该子集的标记，那么将大的节点号标记置为小节点号。
            if(x!=y){   // 防止出现回路
                if(x>y)
                    flag[x] = y;
                else
                    flag[y] = x;
            }
    }

## **三、实例** ##

[CCF 地铁修建][CCF]

[SouthEast]: /images/20210520/c490ad9ad64b45c697a161c283f5ec9d.png
[SouthEast 1]: /images/20210520/e5708d75740843fe968ed927c11336ce.png
[SouthEast 2]: /images/20210520/c302c5ea8510472e8cfe938176eb141b.png
[CCF]: http://blog.csdn.net/qq_16234613/article/details/76795271

发表评论取消回复

表情：

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

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

相关阅读

相关并查集 Ⅱ

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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