684. 冗余连接
- 思路
- example
- 并查集
并查集主要有三个功能。
寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
判断两个节点是否在同一个集合，函数：same(int u, int v)，就是判断两个节点是不是同一个根节点
例2，edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
ancestor = [0, 1, 2, 3, 4, 5], i.e., ancestor[i] = i
edge = [1,2], find(1), find(2), ancestor[find(1)] = ancestor[find(2)], ancestor = [0, 2, 2, 3, 4, 5].
edge = [2,3], find(2), find(3), ancestor[find(2)] = ancestor[find(3)], ancestor = [0, 2, 3, 3, 4, 5].
edge = [3,4], find(3), find(4), ancestor[find(3)] = ancestor[find(4)], ancestor = [0, 2, 3, 4, 4, 5].
edge = [1,4], find(1), find(4), ancestor = [0, 4, 4, 4, 4, 5] (注意这里，把节点1，2，3的ancestor都改为了4). find(1) = find(4) = 4， 找到loop, 删掉这个edge即可
edge = [1,5], 不需要处理
另一个例子
edges = [[1,2], [2,3], [3,4], [2,5]]
ancestor = [0, 1, 2, 3, 4, 5], i.e., ancestor[i] = i
edge = [1,2], find(1), find(2), ancestor[find(1)] = ancestor[find(2)], ancestor = [0, 2, 2, 3, 4, 5].
edge = [2,3], find(2), find(3), ancestor[find(2)] = ancestor[find(3)], ancestor = [0, 2, 3, 3, 4, 5].
edge = [3,4], find(3), find(4), ancestor[find(3)] = ancestor[find(4)], ancestor = [0, 2, 3, 4, 4, 5].
edge = [2,5], find(2), find(5), ancestor[find(2)] = ancestor[find(5)], ancestor = [0, 4, 4, 4, 5, 5].
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
parent = list(range(n+1)) # e.g., parent[1] = 1
def find(node): # 递归, 寻找祖先，并且在寻找的同时把上辈节点全部指向祖先节点 (只需要第一遍连接，后续调用只需最多二步)
if parent[node] != node:
parent[node] = find(parent[node]) # node的parent 就是node的parent的 祖先
return parent[node]
def union(node1, node2): # node1的祖先 指向 node2的祖先
parent[find(node1)] = find(node2)
# main code
for i in range(len(edges)):
node1, node2 = edges[i][0], edges[i][1]
if find(node1) != find(node2): #
union(node1, node2)
else: # already find a loop, edges[i] is redundant
return edges[i]
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
def find(u):
if ancestor[u] != u:
ancestor[u] = find(ancestor[u])
return ancestor[u]
def join(u, v):
ancestor[find(u)] = find(v)
def same(u, v):
return find(u) == find(v)
#
n = len(edges)
ancestor = [i for i in range(n+1)]
for edge in edges:
u, v = edge[0], edge[1]
if same(u, v):
return edge
join(u, v)
- DFS (无向图，检测某条边是否是环的一部分)
例2, edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
先构造graph:
graph[1] = [2, 4, 5]
graph[2] = [1, 3]
graph[3] = [2, 4]
graph[4] = [1, 5]
graph[5] = [1]
倒序dfs遍历edges, 判断：
edge = [1,5], edge[1] = 5, neighbors = [] (不包括edge[0])
edge = [1, 4], edge[1] = 4, neighbors = [5, 1, 2, 3], edge[0] in neighbors: 环
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
def dfs(graph, parent, x, y):
visited.add(x)
for node in graph[x]:
if node == y and x != parent: # 保证[x,y] != [parent, y] (起始边）
return True
if node not in visited:
if dfs(graph, parent, node, y) == True:
return True
return False
graph = collections.defaultdict(list)
for edge in edges:
x, y = edge[0], edge[1]
graph[x].append(y)
graph[y].append(x)
for i in range(len(edges)-1, -1, -1):
x, y = edges[i][0], edges[i][1]
visited = set() #!!!
visited.add(y) # !!!!!!
if dfs(graph, x, x, y) == True:
return edges[i]
- 或者顺序遍历edges，逐次加进graph，DFS (这个效率更高)
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
graph = {}
def dfs(u, v):
visited.add(u) # u当作是起点
for node in graph[u]:
if node == v: # 已经找到环
return True
elif node not in visited:
if dfs(node, v):
return True
return False
for edge in edges:
if edge[0] not in graph:
graph[edge[0]] = {edge[1]}
else:
visited = set()
if dfs(edge[0], edge[1]):
return edge
else:
graph[edge[0]].add(edge[1])
if edge[1] not in graph:
graph[edge[1]] = {edge[0]}
else:
graph[edge[1]].add(edge[0])
