本文主要是介绍代码随想录图论并查集 第七天 | 685.冗余连接II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录图论并查集 第七天 | 685.冗余连接II
一、685.冗余连接II
题目链接:https://leetcode.cn/problems/redundant-connection-ii/
思路:684.冗余连接中是连通且无环的无向图可直接使用并查集模板,如果想判断集合中是否有环,且那条边构成环,只需要每次加入并查集之前先判断一下是否有相同的根,有即构成环。
本题是有向图,如果不是树,有两种情况一种是入度为2,如[1,2]、[1,3]、[2,3]。3的入度为2删掉一条边即为树。另一种是无入度为2的点,本身来说,本题原集合不是树,如果无入度为2那么就一定构成环了,如[1,2]、[2,3]、[3,1]。
那么,分为两步,第一步找到入度为2的点,进行删除尝试,如果没有入度为2的点,开始第二步,找到构成环的边。
class Solution {int[] father = new int[1005];;public int[] findRedundantDirectedConnection(int[][] edges) {int[] inDegree = new int[1005];for (int i = 0; i < edges.length; i++) {inDegree[edges[i][1]]++;}List<Integer> list = new ArrayList<>();for (int i = edges.length -1; i >= 0 ; i--) {if (inDegree[edges[i][1]] == 2) list.add(i);}if (!list.isEmpty()) {if (f1(edges, list.get(0))) return edges[list.get(0)];else return edges[list.get(1)];}return f2(edges);}boolean f1(int[][] edges, int x) {init();for (int i = 0; i < edges.length; i++) {if (i == x) continue;if (isSame(edges[i][0], edges[i][1])) return false;else join(edges[i][0], edges[i][1]);}return true;}int[] f2(int[][] edges) {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) {u = find(u);v = find(v);if (u == v)return;father[u] = v;}boolean isSame(int u, int v) {u = find(u);v = find(v);return u == v;}
}
这篇关于代码随想录图论并查集 第七天 | 685.冗余连接II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!