三点水网站建设合同书,唐山万唯网络科技有限公司,山东淄博网站建设,企业网站如何找词❓ 1971. 寻找图中是否存在路径
难度#xff1a;简单
有一个具有 n 个顶点的 双向 图#xff0c;其中每个顶点标记从 0 到 n - 1#xff08;包含 0 和 n - 1#xff09;。图中的边用一个二维整数数组 edges 表示#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 …❓ 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 。
示例 1 输入n 3, edges [[0,1],[1,2],[2,0]], source 0, destination 2 输出true 解释存在由顶点 0 到顶点 2 的路径: 0 → 1 → 20 → 2 示例 2 输入n 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5 输出false 解释不存在由顶点 0 到顶点 5 的路径. 提示 1 n 2 ∗ 1 0 5 1 n 2 * 10^5 1n2∗105 0 e d g e s . l e n g t h 2 ∗ 1 0 5 0 edges.length 2 * 10^5 0edges.length2∗105 e d g e s [ i ] . l e n g t h 2 edges[i].length 2 edges[i].length2 0 u i , v i n − 1 0 ui, vi n - 1 0ui,vin−1 u i ! v i ui ! vi ui!vi 0 s o u r c e , d e s t i n a t i o n n − 1 0 source, destination n - 1 0source,destinationn−1不存在重复边不存在指向顶点自身的边
思路并查集
们将图中的每个强连通分量视为一个集合强连通分量中任意两点均可达如果两个点 source 和 destination 处在同一个强连通分量中则两点一定可连通因此连通性问题可以使用并查集解决。
并查集主要有三个功能
寻找根节点函数find(int u)也就是判断这个节点的祖先节点是哪个将两个节点****接入到同一个集合函数join(int u, int v)将两个节点连在同一个根节点上判断两个节点是否在同一个集合函数isSame(int u, int v)就是判断两个节点是不是同一个根节点。
并查集初始化时n 个顶点分别属于 n 个不同的集合每个集合只包含一个顶点。初始化之后遍历每条边由于图中的每条边均为双向边因此将同一条边连接的两个顶点所在的集合做合并。
遍历所有的边之后判断顶点 source 和顶点 destination 是否在同一个集合中如果两个顶点在同一个集合则两个顶点连通如果两个顶点所在的集合不同则两个顶点不连通。
代码(C、Java)
C
class Solution {
private:vectorint father;// 初始化并查集void init(int n){father vectorint(n, 0);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){return find(u) find(v);}// 将v-u 这条边加入并查集void join(int u, int v){u find(u); // 寻找 u 的根v find(v); // 寻找 v 的根if(u v) return;father[u] v;}public:bool validPath(int n, vectorvectorint edges, int source, int destination) {if(source destination) return true;init(n);for(int i 0; i edges.size(); i){join(edges[i][0], edges[i][1]);}return isSame(source, destination);}
};Java
class Solution {public boolean validPath(int n, int[][] edges, int source, int destination) {UF uf new UF(n);for(int[] edge :edges) {uf.union(edge[0], edge[1]);}return uf.isConnected(source, destination);}class UF{int[] parent;public UF(int n) {parent new int[n];for(int i 0; i n; i) parent[i] i;}private int find(int x) {if(parent[x] x) return x;return parent[x] find(parent[x]);}public boolean isConnected(int p, int q) {return find(p) find(q);}public void union(int p, int q) {int pRoot find(p), qRoot find(q);if(pRoot ! qRoot) {parent[qRoot] pRoot;}}}
}运行结果 复杂度分析 时间复杂度 O ( n m × α ( m ) ) O(nm×α(m)) O(nm×α(m))其中 n 为图中的顶点数m 是图中边的数目α 是反阿克曼函数。并查集的初始化需要 O ( n ) O(n) O(n)的时间然后遍历 m 条边并执行 m 次合并操作最后对 source 和 destination 执行一次查询操作查询与合并的单次操作时间复杂度是 O ( α ( m ) ) O(α(m)) O(α(m))因此合并与查询的时间复杂度是 O ( m × α ( m ) ) O(m×α(m)) O(m×α(m))总时间复杂度是 O ( n m × α ( m ) ) O(nm×α(m)) O(nm×α(m))。 空间复杂度 O ( n ) O(n) O(n)其中 n 是图中的顶点数。并查集需要 O ( n ) O(n) O(n) 的空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
