Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS solution in Clear category for Node Disconnected Users by suic
from collections import defaultdict
def disconnected_users(edges, values, root, crashed_nodes):
if root in crashed_nodes:
return sum(values.values())
graph = defaultdict(set)
for s, e in edges:
graph[s].add(e)
graph[e].add(s)
users = sum(values[node] for node in dfs(graph, root))
for node in crashed_nodes:
del graph[node]
crashed_nodes = set(crashed_nodes)
for node in graph:
graph[node] -= crashed_nodes
return users - sum(values[node] for node in dfs(graph, root))
def dfs(graph, root):
visited, stack = set(), [root]
while stack:
next_node = stack.pop()
visited.add(next_node)
stack.extend(graph[next_node] - visited)
return visited
May 7, 2017
Comments:
