如果要去掉还是树，那么去掉之后一定是联通分量为1的
因此维护一个neighbour并在遍历某个edge时先remove后add回来即可
然后看联通分量是否为1
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# 去掉之后联通分量仍然是1即可
nodes = set()
neighbour = defaultdict(list)
for x, y in edges:
neighbour[x].append(y)
neighbour[y].append(x)
nodes.add(x)
nodes.add(y)
n = len(nodes)
ans = None
visit = [False] * n
# 联通分量走完
def dfs(node):
nonlocal visit
visit[node - 1] = True
for child in neighbour[node]:
if visit[child - 1] is False:
dfs(child)
for x, y in edges:
visit = [False] * n
# 更新一下neighbour
neighbour[x].remove(y)
neighbour[y].remove(x)
# 遍历所有点
cnt = 0
for node in range(1, n + 1):
if visit[node - 1] is False:
dfs(node)
cnt += 1
#print(cnt)
if cnt == 1:
ans = [x, y]
# 更新一下neighbour
neighbour[x].append(y)
neighbour[y].append(x)
return ans
官方
意思是如果不是同一个联通分量就合并 否则就是多余的边
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
parent = list(range(n + 1))
def find(index: int) -> int:
if parent[index] != index:
parent[index] = find(parent[index])
return parent[index]
def union(index1: int, index2: int):
# 后者作为爸爸
parent[find(index1)] = find(index2)
for node1, node2 in edges:
if find(node1) != find(node2):
union(node1, node2)
else:
# 出现环 也就是破坏它是树的最后一条边
return [node1, node2]
return []
总结
万万没想到
py的并查集这么简洁
如果两个点已经同属一个联通分量 那么当前这条边就是最后的罪魁祸首
