难度: Medium
原题连接
内容描述
In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional 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] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
| |
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.
Update (2017-09-26):
We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph. For the directed graph follow up please see Redundant Connection II). We apologize for any inconvenience caused.
思路 1 - 时间复杂度: O(N * V * E)- 空间复杂度: O(N * V)******
union-find
稍微注意一下我的union-find boilerplate里面的uf是0-based，而这里的点集是1-based
所以要对edges做预处理 edges = [[i-1,j-1] for i, j in edges]
具体思想就是去掉一条边后看是否为树，即无环且full connected
因为用union-find我们是通过判断所有访问的点是否都是同一个parent来看是否full connected，所以full connected是肯定保证了的
beats 14.55%
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 hasCycle(self):
for node1, node2 in self.edges:
if self.find(node1, self.uf) == self.find(node2, self.uf): # cycle exists
return True
else:
self.union(node1, node2, self.uf)
return False
def fullyConnected(self):
self.hasCycle() # 必须先调用一下这段代码实现preprocess
return len(set(self.find(i, self.uf) for i in self.uf)) == 1 # fully connected
class Solution:
def findRedundantConnection(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 not graph.hasCycle():
x, y = edges[i]
return [x+1, y+1]思路 2 - 时间复杂度: O(N * (V + E))- 空间复杂度: O(N * V)******
DFS, 具体思想就是去掉一条边后看是否为树，即无环且full connected
因为用DFS我们是通过判断是否所有的点我们都访问到了来看是否full connected，所以full connected是无法保证的
用DFS我们是以某一个点为入口往下进行深度遍历，但是如果我们用来作为入口的这个点正好被我们删除了呢？即，如果我们删除掉这条边的话， 这个点就与图中所有的点都隔离开了呢？
例如输入为
10
[[2,7],[7,8],[3,6],[2,5],[6,8],[4,8],[2,8],[1,8],[7,10],[3,9]]
删除边[1,8]，这样还会有环，2 -> 7 -> 8 -> 2，假如我们像union-find一样只判断if not graph.hasCycle()的话，答案是错的
因为我们从入口1（即原始input中的点0）出发，我们一个点都到不了，程序自然说没有环了，如果我们傻傻地返回[1,8]为答案就错了
因此正确的做法是要先确定删除这条边以后我们整个图还是full connected的，即从入口还是可以一直访问下去的，而且还要保证删除这条边之后我们没有环了
beats 14.55%
class Graph(object):
def __init__(self, vertex_cnt, edges):
self.vertex_cnt = vertex_cnt
self.graph = collections.defaultdict(list)
self.visited = [False] * self.vertex_cnt
for node1, node2 in edges:
self.addEdge(node1, node2)
def addEdge(self, v1, v2):
self.graph[v1].append(v2)
self.graph[v2].append(v1)
def hasCycleHelper(self, v, visited, prev_v):
self.visited[v] = True
for i in self.graph[v]:
if not visited[i]:
if self.hasCycleHelper(i, visited, v):
return True
else:
if i != prev_v:
return True
return False
def hasCycle(self):
if self.hasCycleHelper(0, self.visited, -1):
return True
return False
def fullyConnected(self):
return all(self.visited)
class Solution:
def findRedundantConnection(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 not graph.hasCycle() and graph.fullyConnected():
x, y = edges[i]
return [x+1, y+1]思路 3 - 时间复杂度: O(N * E)- 空间复杂度: O(N)******
但是其实我们这样想，如果我们从edges逆序开始遍历，不断地组成一个图，当碰到一条边(u, v)的时候，如果这个时候我们其实已经可以从u走到v了，说明在碰到这条边之前u和v就已经是联通的，那么说明当前这条边是duplicate
union_find, beats 54.83%
class UnionFind(object):
def uf(self, n): # 初始化uf数组和组数目
self.count = n
self.uf = [i for i in range(n)]
self.size = [1] * n # 每个联通分量的size
def find(self, x): # 判断节点所属于的组
while x != self.uf[x]:
self.uf[x] = self.uf[self.uf[x]]
x = self.uf[x]
return self.uf[x]
def union(self, x, y): # 连接两个节点
x_root = self.find(x)
y_root = self.find(y)
if x_root != y_root:
self.size[y_root] += self.size[x_root]
self.uf[x_root] = y_root
self.count -= 1
def connected(self, x, y): # 判断两个节点是否联通
return self.find(x) == self.find(y)
class Solution:
def findRedundantConnection(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]))
unionfind = UnionFind()
unionfind.uf(n)
for node1, node2 in edges:
if not unionfind.connected(node1, node2):
unionfind.union(node1, node2)
else:
return [node1+1, node2+1]思路 4 - 时间复杂度: O(N * E)- 空间复杂度: O(N)******
同样的道理，我们可以用DFS来实现, beats 28.39%
class Solution:
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
graph = collections.defaultdict(list)
def dfs(source, target):
if source not in visited:
visited.add(source)
if source == target:
return True
return any(dfs(nei, target) for nei in graph[source])
for u, v in edges:
visited = set()
if u in graph and v in graph and dfs(u, v):
return u, v
graph[u].append(v)
graph[v].append(u)