代码训练营 day59|并查集

前言

这里记录一下陈菜菜的刷题记录，主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕，一年车企软件开发经验
代码能力：有待提高
常用语言：C++

系列文章目录

第59天 ：第十一章：图论part05

---

`

---

---

一、今日任务

● 并查集理论基础
● 寻找存在的路径

二、详细布置

并查集理论基础

并查集常用来解决连通性问题。我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：
将两个元素添加到一个集合中。
判断两个元素在不在同一个集合

模板

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}

通过模板，我们可以知道，并查集主要有三个功能。
1.寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
2.将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在 同一个根节点上
3.判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

拓展

在「路径压缩」讲解中，我们知道如何靠压缩路径来缩短查询根节点的时间。
其实还有另一种方法：按秩（rank）合并。
rank表示树的高度，即树中结点层次的最大值。

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;rank[i] = 1; // 也可以不写}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树else father[v] = u;if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}

107. 寻找存在的路径

题目链接：力扣107
文章讲解：代码随想录

给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

输入：
第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。
后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。
最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。
输出：
输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。

提示：

数据范围：

1 <= M, N <= 100

样例1：

输入：
5 4
1 2
1 3
2 4
3 4
1 4
输出：
1

思路

这题模板题。

实战

#include<iostream>
#include<vector>
using namespace std;
int n = 105; 
vector<int> father = vector<int> (n, 0); void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}int main(){int n,m,s,t;cin>>n>>m;init();for(int i=0;i<m;i++){cin>>s>>t;join(s,t);}int begin,end;cin>>begin>>end;if(isSame(begin,end))cout<<1<<endl;elsecout<<0<<endl;
}

总结

今天主要学习了并查集的一系列操作，感觉并查集很好理解，模板记忆一下。主要是压缩路径。
加油，坚持打卡的第59天。