做数据同步的两个网站,网站制作公司教你怎么制作网站,市场营销策划书模板,江西住房和城乡建设部网站首页并查集
并查集主要有三个功能。
寻找根节点#xff0c;函数#xff1a;find(int u)#xff0c;也就是判断这个节点的祖先节点是哪个将两个节点接入到同一个集合#xff0c;函数#xff1a;join(int u, int v)#xff0c;将两个节点连在同一个根节点上判断两个节点是否在…并查集
并查集主要有三个功能。
寻找根节点函数find(int u)也就是判断这个节点的祖先节点是哪个将两个节点接入到同一个集合函数join(int u, int v)将两个节点连在同一个根节点上判断两个节点是否在同一个集合函数isSame(int u, int v)就是判断两个节点是不是同一个根节点
并查集可以解决的问题两个节点是否在一个集合也可以将两个节点添加到一个集合中。
难点在于根的路径压缩的理解 寻找图中是否存在路径
1971. 寻找图中是否存在路径
有一个具有 n 个顶点的 双向 图其中每个顶点标记从 0 到 n - 1包含 0 和 n - 1。图中的边用一个二维整数数组 edges 表示其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 source 开始到顶点 destination 结束的 有效路径 。
给你数组 edges 和整数 n、source 和 destination如果从 source 到 destination 存在 有效路径 则返回 true否则返回 false 。
class Solution {
public:bool validPath(int n, vectorvectorint edges, int source, int destination) {/*深搜 / 广搜这里选择使用并查集进行实现使用并查集判断两个元素是否在同一个集合内部step1: 使用join(u,v)把每条边加入到并查集step2: 使用 isSame(int u,int v) 判断是否是同一个根【即是否属于同一个集合】*/// step0: 并查集初始化init(n);// step1: 把每条边加入并查集for(vectorint edge : edges) { // 每个元素就是一条边join(edge[0],edge[1]);}// step2: 使用 isSame(int u,int v) 判断是否是同一个根return isSame(source, destination);}
private:vectorint father vectorint(200001,0) ; // 按照节点的大小定义数组长度void init(int n) { // 并查集初始化for(int i 1; 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 这条边加入并查集 father[v] uvoid join(int u, int v) {// 先判断两个元素是否在同一个集合内部u find(u);v find(v);if(u v) return;father[v] u;}
};
冗余连接
684. 冗余连接
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges edges[i] [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案则返回数组 edges 中最后出现的那个。
class Solution {public int[] findRedundantConnection(int[][] edges) {/**图论删除相对于数来说的多余的一条边使用并查集的思想把每条边都加入到其中如果在加入的时候发现两个顶点已经同根即在一个并查集中此时就说明这条边是一条冗余边删除这条边即可*/int[] ans null;init(edges.length);for(var edge : edges) {if(!join(edge[0],edge[1])) {ans edge;break;}}return ans;}private int[] father;private void init(int vLen) { // 并查集的初始化 // 传入顶点数father new int[vLen1];for(int i0; i vLen; i) {father[i] i; // father[i] i; 自身是自身的根即刚开始所有节点都是单项的}}// 找到一个元素的根int find(int u) {return father[u] u ? u: (father[u] find(father[u]));}// 把 u-v 加入并查集private boolean join(int u, int v) {u find(u);v find(v);if(u v) return false;father[u] v;return true;}// 判断两个节点是否同根public boolean isSame(int u, int v) {u find(u);v find(v);return u v;}
}
