网站开发工程师绩效,江苏省工程建设标准站网站,台州做网站哪家公司好,构建网站无障碍建设代码随想录图论并查集 | 第六天 1971. 寻找图中是否存在路径 684.冗余连接
一、1971. 寻找图中是否存在路径
题目链接#xff1a;https://leetcode.cn/problems/find-if-path-exists-in-graph/ 思路#xff1a;典型并查集模板题。
class Solution {int[] father null;pub…代码随想录图论并查集 | 第六天 1971. 寻找图中是否存在路径 684.冗余连接
一、1971. 寻找图中是否存在路径
题目链接https://leetcode.cn/problems/find-if-path-exists-in-graph/ 思路典型并查集模板题。
class Solution {int[] father null;public boolean validPath(int n, int[][] edges, int source, int destination) {father new int[n];init(n);for (int[] edge : edges) {join(edge[0], edge[1]);}return isSame(source, destination);}void init(int n) {for (int i 0; i n; i) {father[i] i;}}int find(int u) {if (father[u] u) return u;return father[u] find(father[u]);}boolean isSame(int u, int v) {u find(u);v find(v);return u v;}void join(int u, int v) {u find(u);v find(v);if (u v)return;father[v] u;}
}二、684.冗余连接
题目链接https://leetcode.cn/problems/redundant-connection/ 思路并查集模板题把有环的集合去掉一条边变成无环的往father数组里join的过程就是添加树的过程如果要添加的两个元素根节点一样那就不要再加了可以返回了加了就变环了。
class Solution {int[] father null;public int[] findRedundantConnection(int[][] edges) {father new int[1005];init();for (int[] edge : edges) {if (isSame(edge[0], edge[1])) return edge;else join(edge[0], edge[1]);}return null;}void init() {for (int i 0; i father.length; i) {father[i] i;}}int find(int u) {if (father[u] u) return u;return father[u] find(father[u]);}void join(int u, int v) {v find(v);u find(u);if (v u) return;father[v] u;}boolean isSame(int u, int v) {u find(u);v find(v);return u v;}
}
