685 Redundant Connection II
685. Redundant Connection II
题目： https://leetcode.com/problems/redundant-connection-ii/
难度 : Hard
我们先定义一下，每条边的第一个点是parent，第二个点是child，例如 2 -> 1 中 node 2 就是 parent，而 node 1 就是 child
明确这个之后，我们要知道图中有一条边是 invalid 的，去除它之后整个图就变成了一棵树，那么什么情况下一个边会导致树变成图呢：
- 如果一个child 在此之前已经有过一个parent了，那么意味着它有两个parent，这在树中肯定是不合法的。
在代码中体现为
node_parent[child] != child，这说明在碰到此时的parent之前我们就已经更新过node_parent[child]了，即child之前已经有一个parent了 - 如果一个child 的 parent 的 parent（或者一直往上找） 就是 child 本身，那么这意味着有环，这在树中也肯定是不合法的。
在代码中体现为
find(node_parents, parent) == child, 这说明child的parent的parent或以上就是child本身，即有环。 例如1 --> 2 --> 1或者1 --> 2 --> 3 --> 1
因此我们可以定义一个列表 node_parent，在最开始的时候，此列表的 index 和 value 一一相等。
然后我们对edges进行第一轮遍历（正序遍历），并且用count来计数不合法的边： - 如果只找到一条不合法的边，那么直接返回它即可 - 如果有超过一条不合法的边，那么我们就进行第二轮遍历（逆序遍历），返回碰到的第一条不合法的边， 这里是为了节约时间，因为如题意我们要返回的是最后一条出现的边，那么我们逆序就更省时间嘛
class Solution(object):
def findRedundantDirectedConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
def find(node_parent, parent):
return parent if node_parent[parent] == parent else find(node_parent, node_parent[parent])
n, count = len(edges), 0 # 用 count 来计数不合法的边
node_parent = [i for i in range(n+1)]
res = [0, 0]
# 第一轮查找不合法的边 （正序）
for i in range(n):
parent, child = edges[i][0], edges[i][1]
if node_parent[child] != child or find(node_parent, parent) == child:
res = edges[i]
count += 1
else:
node_parent[child] = parent
if count == 1: # 如果只有一条不合法的边，直接返回
return res
# 重置 node_parent 并开始第二轮查找 （逆序）
node_parent = [i for i in range(n+1)]
for i in range(n-1, -1, -1):
parent, child = edges[i][0], edges[i][1]
if node_parent[child] != child or find(node_parent, parent) == child:
return edges[i]
else:
node_parent[child] = parent
return res
这道题感谢xyzxuyizhen大佬， 看到他的思路才逃离了我之前的很复杂的想法。
