并查集的简单实现代码模板

柔光的暖阳◎ 2023-07-12 05:05 24阅读 0赞

1 #include <iostream>
     2 #include <cstdio>
     3 
     4 using namespace std;
     5 
     6 const int max_n = 1000;
     7 
     8 int par[max_n];
     9 int ranks[max_n];
    10 
    11 void init(int n)
    12 {
    13     for(int i=0;i<n;++i)
    14     {
    15         par[i]=i;
    16         ranks[i]=0;
    17     }
    18 }
    19 
    20 int find(int x)
    21 {
    22     if(par[x]==x)
    23     {
    24         return x;
    25     }
    26     else
    27     {
    28         return par[x]=find(par[x]);
    29     }
    30 }
    31 
    32 
    33 // 合并
    34 void unite(int x,int y)
    35 {
    36     x=find(x);
    37     y=find(y);
    38     if(x==y)
    39     {
    40         return;
    41     }
    42 
    43     if(ranks[x]<ranks[y])
    44     {
    45         par[x]=y;
    46     }
    47     else
    48     {
    49         par[y]=x;
    50         if(ranks[x]==ranks[y])
    51         {
    52             ++ ranks[x];
    53         }
    54     }
    55 }
    56 
    57 
    58 bool same(int x,int y)
    59 {
    60     return find(x)==find(y);
    61 }
    62 
    63 
    64 int main()
    65 {
    66 
    67     return 0;
    68 }

发表评论取消回复

表情：

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

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

相关阅读

相关并查集的简单实现代码模板

1 include <iostream> 2 include <cstdio> 3 4 using namespace std;

柔光的暖阳◎/ 2023年07月12日 05:05/ 0 赞/ 25 阅读

相关并查集(模板)

并查集(模板) [来源][Link 1] 并查集：将不同分散的结点，通过某种关系将他们连接成一个森林并查集分为3步： 1. 并：给出两点关系，如果属于同

蔚落/ 2023年06月01日 06:11/ 0 赞/ 109 阅读

相关一篇并查集代码模板及经典例题

一、定义并查集就是对集合进行合并及查询，包括两部分，并（union）和查（find）。 “并”是将有关联的元素合并为一个集合，“查”是查找这个元素属于哪个集合。路径

Myth丶恋晨/ 2023年02月13日 03:50/ 0 赞/ 114 阅读

相关并查集--简单记录

并查集也是一种树状结构，用于处理一些不相交集合的合并以及查询问题查询： int find(int x) { while(x!=parent[x

骑猪看日落/ 2023年01月22日 10:58/ 0 赞/ 83 阅读

相关数据结构——并查集(C代码实现)

目录结构定义结构操作不同的算法实现 Quick-Find算法 Quick-Union算法结构定义并查集本

た入场券/ 2022年12月28日 04:20/ 0 赞/ 175 阅读

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

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

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

相关代码笔记：并查集

/\ 题意还原：给出图中各结点的连通关系，然后判断每减少一个结点，对图中其它结点连通关系的影响思路：用并查集辅助记录连通子图的个数，然后逐渐减少结点，判断图中结点的连

亦凉/ 2022年06月17日 02:50/ 0 赞/ 199 阅读

相关 1073 家族（并查集模板）

题目描述 Description 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲

﹏ヽ暗。殇╰゛Y/ 2022年06月15日 00:37/ 0 赞/ 282 阅读

相关模板--并查集

问题描述： Mr Wang wants some boys to help him with a project. Because the project is ra

雨点打透心脏的1/2处/ 2022年06月11日 04:21/ 0 赞/ 274 阅读

相关并查集实现

并查集是什么东西？它是用来管理元素分组情况的一种数据结构。他可以高效进行两个操作： 1. 查询a，b是否在同一组 2. 合并a和b所在的组萌新可能不知所云，这

深碍√TFBOYSˉ_/ 2022年05月13日 11:26/ 0 赞/ 232 阅读