代码随想录图论并查集 | 第六天 1971. 寻找图中是否存在路径 684.冗余连接

本文主要是介绍代码随想录图论并查集 | 第六天 1971. 寻找图中是否存在路径 684.冗余连接，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录图论并查集 | 第六天 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;}
}