做网站有意思吗?,北京天津网站建设,免费网站申请注册步骤,临淄信息网最新招聘小时工前言
这里记录一下陈菜菜的刷题记录#xff0c;主要应对25秋招、春招 个人背景 211CS本CUHK计算机相关硕#xff0c;一年车企软件开发经验 代码能力#xff1a;有待提高 常用语言#xff1a;C
系列文章目录
第59天 #xff1a;第十一章#xff1a;图论part05 文章目录…前言
这里记录一下陈菜菜的刷题记录主要应对25秋招、春招 个人背景 211CS本CUHK计算机相关硕一年车企软件开发经验 代码能力有待提高 常用语言C
系列文章目录
第59天 第十一章图论part05 文章目录 前言系列文章目录第59天 第十一章图论part05 一、今日任务二、详细布置并查集理论基础模板拓展 107. 寻找存在的路径提示样例1思路实战 总结 一、今日任务
● 并查集理论基础 ● 寻找存在的路径
二、详细布置
并查集理论基础
并查集常用来解决连通性问题。我们需要判断两个元素是否在同一个集合里的时候我们就要想到用并查集。
并查集主要有两个功能 将两个元素添加到一个集合中。 判断两个元素在不在同一个集合
模板
int n 1005; // n根据题目中节点数量而定一般比节点数量大一点就好
vectorint father vectorint (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根据题目中节点数量而定一般比节点数量大一点就好
vectorint father vectorint (n, 0); // C里的一种数组结构
vectorint rank vectorint (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 和 MN 代表节点的个数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思路
这题模板题。
实战
#includeiostream
#includevector
using namespace std;
int n 105;
vectorint father vectorint (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;cinnm;init();for(int i0;im;i){cinst;join(s,t);}int begin,end;cinbeginend;if(isSame(begin,end))cout1endl;elsecout0endl;
}总结
今天主要学习了并查集的一系列操作感觉并查集很好理解模板记忆一下。主要是压缩路径。 加油坚持打卡的第59天。
