# Участник:Hellhoundmipt/redundant-connection-ii

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
```def bfs(s, edge_dict, node_set, find_redundant_edge=False):
level = {node: -1 for node in node_set}
level[s] = 0
queue = [s]
while queue:
v = queue.pop(0)
for w in edge_dict[v]:
if level[w] is -1:
queue.append(w)
level[w] = level[v] + 1
elif find_redundant_edge:
return [v, w]
return level

def is_root(node, edge_dict, node_set):
level = bfs(node, edge_dict, node_set)
for v in level:
if level[v] == -1:
return False
return True

class Solution:
# we assume that the graph without a redundant is a rooted tree
def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
node_set = set([item for sublist in edges for item in sublist])
edge_dict = {node: [] for node in node_set}
for edge in edges:
edge_dict[edge[0]].append(edge[1])

for node in node_set:
if is_root(node, edge_dict, node_set):
root = node
break

return bfs(root, edge_dict, node_set, find_redundant_edge=True)```