用了并查集,分成有入度为2以及有环两种情况。
class Solution: def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]: n = len(edges) indegrees = {k + 1: 0 for k in range(n)} for u, v in edges: indegrees[v] += 1 for i in range(n - 1, -1, -1): u, v = edges[i] if indegrees[v] == 2 and self.validTreeExceptN(edges, i): return edges[i] for i in range(n - 1, -1, -1): u, v = edges[i] if indegrees[v] == 1 and self.validTreeExceptN(edges, i): return edges[i] return None def validTreeExceptN(self, edges, n): def find(fa, i): if fa[i] != i: fa[i] = find(fa, fa[i]) return fa[i] def union(fa, i, j): fa[j] = find(fa, i) # union-find set fa = [0] * (len(edges) + 1) for i in range(len(fa)): fa[i] = i # valid tree with out edge n cnt = len(edges) for i in range(len(edges)): if i == n: continue u, v = edges[i] fu = find(fa, u) fv = find(fa, v) if fu != fv: union(fa, v, u) cnt -= 1 return cnt == 1