Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS on colored network graph without crashed nodes solution in Clear category for Node Disconnected Users by Phil15
def disconnected_users(net, users, source, crushes):
if source in crushes:
return sum(users.values())
not_crashed = set(users) - set(crushes)
# G is the network graph without crashed nodes
G = {node: {user for user in not_crashed
if [node, user] in net or [user, node] in net}
for node in not_crashed}
# DFS on G with color for all users
color = {user: False for user in users}
def dfs(s):
color[s] = True
for son in G[s]:
if not color[son]:
dfs(son)
dfs(source)
# Just have to sum users on those not-colored/disconnected nodes.
return sum(users[user] for (user, colored) in color.items()
if not colored)
Sept. 6, 2018
