每日算法系列【LeetCode 685】冗余连接 II

每日算法系列【LeetCode 685】冗余连接 II

题目描述

示例1

输入：[[1,2], [1,3], [2,3]]输出：[2,3]解释： 1 / \v v2-->3

示例2

输入：[[1,2], [2,3], [3,4], [4,1], [1,5]]输出：[4,1]解释：5 <- 1 -> 2 ^ | | v 4 <- 3

提示

代码

c++

class Solution {public: static const int N = 1010; int f[N], degree[N]; int n; vector findRedundantDirectedConnection(vector>& edges) { n = edges.size(); memset(degree, 0, sizeof degree); for (auto e : edges) ++degree[e[1]]; for (int i = n-1; i >= 0; --i) { if (degree[edges[i][1]] == 2 && !wrongEdge(edges, i).size()) { return edges[i]; } } return wrongEdge(edges, n); } vector wrongEdge(vector>& edges, int except) { init(); for (int i = 0; i < n; ++i) { if (i == except) continue; int u = edges[i][0], v = edges[i][1]; if (same(u, v)) return edges[i]; join(u, v); } return {}; } void init() { for (int i = 1; i <= n; ++i) { f[i] = i; } } int find(int u) { return u==f[u] ? u : f[u]=find(f[u]); } void join(int u, int v) { u = find(u); v = find(v); if (u == v) return; f[v] = u; } bool same(int u, int v) { u = find(u); v = find(v); return u == v; }};

python

class Solution: def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]: self.n = len(edges) degree = [0] * (self.n+1) for u, v in edges: degree[v] += 1 for u, v in edges[::-1]: if degree[v] == 2 and len(self.wrongEdge(edges, [u, v])) == 0: return [u, v] return self.wrongEdge(edges, []) def wrongEdge(self, edges, ex): self.f = [i for i in range(self.n+1)] for u, v in edges: if [u, v] == ex: continue if self.same(u, v): return [u, v] self.join(u, v) return [] def find(self, u): if u == self.f[u]: return u self.f[u] = self.find(self.f[u]) return self.f[u] def join(self, u, v): u, v = self.find(u), self.find(v) if u == v: return self.f[v] = u def same(self, u, v): u, v = self.find(u), self.find(v) return u == v

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。