szymcio32
10/25/2019 - 3:42 PM

Przejście grafu (graph traversal) - Depth First Search - DFS


def disconnected_users(links, users, start, crashed):
    graph = dict()
    visited = set()

    for link in links:
        graph.setdefault(link[0], set()).add(link[1])
        graph.setdefault(link[1], set()).add(link[0])

    def dig(node):
        if node in crashed:
            return
            
        visited.add(node)

        for nextNode in graph[node]:
            if nextNode not in visited:
                dig(nextNode)

    dig(start)

    return sum(num for node, num in users.items() if node not in visited)