难度: Hard
原题连接
内容描述
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.
Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
1
/ \
v v
2-->3
Example 2:
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
^ |
| v
4 <- 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
思路 1 - 时间复杂度: O(V * E^2)- 空间复杂度: O(V)******
当我们发现两种情况的时候，证明当前这条边在树中是非法的：
- 如果一个child 在遇到当前边之前已经有过一个parent了，那么意味着它有两个parent，这在树中肯定是不合法的。
在代码中体现为
self.uf[child] != child，这说明在碰到此时的parent之前我们就已经更新过self.uf[child]了，即child之前已经有一个parent了 - 如果一个child 的 parent 的 parent（或者一直往上找） 就是 child 本身，那么这意味着有环，这在树中也肯定是不合法的。
在代码中体现为
self.find(parent, self.uf) == child, 这说明child的parent的parent或以上就是child本身，即有环。 例如1 --> 2 --> 1或者1 --> 2 --> 3 --> 1
因此我们按照逆序删除掉一条边，如果剩下的所有的边能够构成一棵合法的树的时候说明删掉的这条边是非法的边
用模版改改，beats 1.00%，有点尴尬
class Graph:
def __init__(self, n, edges):
self.edges = edges
self.n = n
self.uf = [i for i in range(n)]
def find(self, x, uf):
while x != uf[x]:
uf[x] = uf[uf[x]]
x = uf[x]
return uf[x]
def union(self, x, y, uf):
x_root = self.find(x, uf)
y_root = self.find(y, uf)
uf[x_root] = y_root
def isTree(self):
for parent, child in self.edges:
if self.uf[child] != child: # 两个不同的parent
return False
elif self.find(parent, self.uf) == child: # parent是自己
return False
else:
self.union(child, parent, self.uf)
return True
class Solution:
def findRedundantDirectedConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
edges = [[i-1,j-1] for i, j in edges]
n = len(set([i for i,j in edges] + [j for i,j in edges]))
for i in range(len(edges)-1, -1, -1):
graph = Graph(n, edges[:i]+edges[i+1:])
if graph.isTree():
x, y = edges[i]
return [x+1, y+1]思路 2 - 时间复杂度: O(V * E)- 空间复杂度: O(V)******
如果对于每一对边(u, v)，我们都将u看成是v的parent，然后逆序遍历edges，慢慢地用union_find构造我们的图，
我们先定义一下，每条边的第一个点是parent，第二个点是child，例如 2 -> 1 中 node 2 就是 parent，而 node 1 就是 child
明确这个之后，我们要知道图中有一条边是 invalid 的，去除它之后整个图就变成了一棵树，那么什么情况下一个边会导致树变成图呢：
- 如果一个child 在遇到当前边之前已经有过一个parent了，那么意味着它有两个parent，这在树中肯定是不合法的。
在代码中体现为
self.uf[child] != child，这说明在碰到此时的parent之前我们就已经更新过self.uf[child]了，即child之前已经有一个parent了 - 如果一个child 的 parent 的 parent（或者一直往上找） 就是 child 本身，那么这意味着有环，这在树中也肯定是不合法的。
在代码中体现为
self.find(parent, self.uf) == child, 这说明child的parent的parent或以上就是child本身，即有环。 例如1 --> 2 --> 1或者1 --> 2 --> 3 --> 1
因此我们可以定义一个列表 node_parent，在最开始的时候，此列表的 index 和 value 一一相等。
然后我们对edges进行第一轮遍历（正序遍历），并且用count来计数不合法的边：
- 如果只找到一条不合法的边，那么直接返回它即可
- 如果有超过一条不合法的边，那么我们就进行第二轮遍历（逆序遍历），返回碰到的第一条不合法的边， 这里是为了节约时间，因为如题意我们要返回的是最后一条出现的边，那么我们逆序就更省时间嘛
beats 97.34%
class Solution:
def findRedundantDirectedConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
def find(x, uf):
while x != uf[x]:
uf[x] = uf[uf[x]]
x = uf[x]
return uf[x]
count = 0 # 用 count 来计数不合法的边
uf = [i for i in range(len(edges)+1)]
res = [0, 0]
# 第一轮查找不合法的边 （正序）
for parent, child in edges:
if uf[child] != child or find(parent, uf) == child:
res = [parent, child]
count += 1
else:
uf[child] = parent
if count == 1: # 如果只有一条不合法的边，直接返回
return res
# 重置 uf 并开始第二轮查找 （逆序）
uf = [i for i in range(len(edges)+1)]
for parent, child in edges[::-1]:
if uf[child] != child or find(parent, uf) == child:
return [parent, child]
else:
uf[child] = parent
return res这道题感谢xyzxuyizhen大佬， 看到他的思路才逃离了我之前的很复杂的想法。