Graph/src/disjoint_set.cpp · CodingPanda/数据结构(C++模板实现)

代码拉取完成,页面将自动刷新

扫描微信二维码支付

取消

支付完成

richgiteeai

Watch

不关注关注所有动态仅关注版本发行动态关注但不提醒动态

1 Star 0 Fork 127

CodingPanda/数据结构(C++模板实现)

forked from cyberdash/数据结构(C++模板实现)

代码 Issues 0 Wiki 统计流水线

服务

加入 Gitee

与超过 1400万开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)

免费加入

已有帐号? 立即登录

文件

master

分支 (3)

管理

master

Prometheus

dev

克隆/下载

HTTPS SSH SVN SVN+SSH 下载ZIP

提示

下载代码请复制以下命令到终端执行

为确保你提交的代码身份被 Gitee 正确识别,请执行以下命令完成配置

git config --global user.name userName 
git config --global user.email userEmail

初次使用 SSH 协议进行代码克隆、推送等操作时,需按下述提示完成 SSH 配置

1 生成 RSA 密钥

2 获取 RSA 公钥内容,并配置到 SSH公钥中

在 Gitee 上使用 SVN,请访问使用指南

使用 HTTPS 协议时,命令行会出现如下账号密码验证步骤。基于安全考虑,Gitee 建议配置并使用私人令牌替代登录密码进行克隆、推送等操作

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # 私人令牌

分支 3

标签 0

data-structures-cpp

Graph

src

disjoint_set.cpp

disjoint_set.cpp 2.18 KB

/*!
 * @file disjoint_set.cpp
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 并查集.cpp文件
 * @version 0.2.1
 * @date 2021年02月21日
 */

#include "disjoint_set.h"

/*!
 * @brief **构造函数**
 * @note
 * 构造函数
 * -------
 * -------
 *
 * -------
 */
DisjointSet::DisjointSet(int size) {
 size_ = size;
 this->parent_ = new int[this->size_];
 for (int i = 0; i < size; i++) {
 parent_[i] = -1;
 }
}

/*!
 * @brief **查找(非递归)**
 * @param index 数组索引
 * @return 根节点
 * @note
 * 查找(非递归)
 * ----------
 * ----------
 *
 * ----------
 */
int DisjointSet::FindNonRecursive(int index) {

while (parent_[index] >= 0) {
 index = parent_[index];
 }

return index;
}

/*!
 * @brief **查找(递归)**
 * @param index 数组索引
 * @return 根节点
 * @note
 * 查找(递归)
 * ---------
 * ---------
 *
 * ---------
 */
int DisjointSet::Find(int index) {
 if (parent_[index] < 0) {
 return index;
 }

return Find(parent_[index]);
}

/**
 * @brief 合并集合(Weighted)
 * @param node1 结点1
 * @param node2 结点2
 * @note
 * 合并集合(Weighted)
 * -----------------
 * -----------------
 *
 * -----------------
 */
void DisjointSet::WeightedUnion(int node1, int node2) {
 int root1 = Find(node1);
 int root2 = Find(node2);

if (root1 == root2) {
 return;
 }

int weighted_union_root = parent_[root1] + parent_[root2];

if (parent_[root2] < parent_[root1]) {
 parent_[root1] = root2;
 parent_[root2] = weighted_union_root;
 } else {
 parent_[root2] = root1;
 parent_[root1] = weighted_union_root;
 }
}

/*!
 * @brief **合并**
 * @param node1 结点1
 * @param node2 结点2
 * @note
 * 合并
 * ----
 * ----
 *
 * ----
 * + **1 获取根结点**\n
 * &emsp; 获取node1的根结点root1\n
 * &emsp; 获取node2的根结点root2\n
 * + **2 判断是否已在同一集合**\n
 */
void DisjointSet::Union(int node1, int node2) {
 int root1 = Find(node1);
 int root2 = Find(node2);

if (root1 == root2) {
 return;
 }

parent_[root1] += parent_[root2];
 parent_[root2] = root1; // 将根root2连接到另一根root1下面
}

一键复制编辑原始数据按行查看历史

Y_Dash 提交于 2023年02月02日 00:42 +08:00 . 邻接表图, 并查集等代码微调

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

/*!
 * @file disjoint_set.cpp
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 并查集.cpp文件
 * @version 0.2.1
 * @date 2021年02月21日
 */

#include "disjoint_set.h"


/*!
 * @brief **构造函数**
 * @note
 * 构造函数
 * -------
 * -------
 *
 * -------
 */
DisjointSet::DisjointSet(int size) {
 size_ = size;
 this->parent_ = new int[this->size_];
 for (int i = 0; i < size; i++) {
 parent_[i] = -1;
 }
}


/*!
 * @brief **查找(非递归)**
 * @param index 数组索引
 * @return 根节点
 * @note
 * 查找(非递归)
 * ----------
 * ----------
 *
 * ----------
 */
int DisjointSet::FindNonRecursive(int index) {

 while (parent_[index] >= 0) {
 index = parent_[index];
 }

 return index;
}


/*!
 * @brief **查找(递归)**
 * @param index 数组索引
 * @return 根节点
 * @note
 * 查找(递归)
 * ---------
 * ---------
 *
 * ---------
 */
int DisjointSet::Find(int index) {
 if (parent_[index] < 0) {
 return index;
 }

 return Find(parent_[index]);
}


/**
 * @brief 合并集合(Weighted)
 * @param node1 结点1
 * @param node2 结点2
 * @note
 * 合并集合(Weighted)
 * -----------------
 * -----------------
 *
 * -----------------
 */
void DisjointSet::WeightedUnion(int node1, int node2) {
 int root1 = Find(node1);
 int root2 = Find(node2);

 if (root1 == root2) {
 return;
 }

 int weighted_union_root = parent_[root1] + parent_[root2];

 if (parent_[root2] < parent_[root1]) {
 parent_[root1] = root2;
 parent_[root2] = weighted_union_root;
 } else {
 parent_[root2] = root1;
 parent_[root1] = weighted_union_root;
 }
}


/*!
 * @brief **合并**
 * @param node1 结点1
 * @param node2 结点2
 * @note
 * 合并
 * ----
 * ----
 *
 * ----
 * + **1 获取根结点**\n
 * &emsp; 获取node1的根结点root1\n
 * &emsp; 获取node2的根结点root2\n
 * + **2 判断是否已在同一集合**\n
 */
void DisjointSet::Union(int node1, int node2) {
 int root1 = Find(node1);
 int root2 = Find(node2);

 if (root1 == root2) {
 return;
 }

 parent_[root1] += parent_[root2];
 parent_[root2] = root1; // 将根root2连接到另一根root1下面
}