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

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/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)