Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Another BFS solution in Clear category for Node Disconnected Users by swagg010164
from collections import deque
def disconnected_users(net, users, source, crushes):
graph = {}
for item in net:
first, second = item[0], item[1]
if first in graph:
graph[first].add(second)
else:
graph[first] = set(second)
if second in graph:
graph[second].add(first)
else:
graph[second] = set(first)
disconnected = 0
conn = {source}
queue = deque([source])
while queue:
cur_v = queue.popleft()
for neigh_v in graph[cur_v]:
if neigh_v not in crushes and neigh_v not in conn:
queue.append(neigh_v)
conn.add(neigh_v)
for k in crushes:
if k == source:
disconnected = sum(users.values())
break
else:
used = {k}
disconnected += users[k]
queue = deque([k])
while queue:
cur_v = queue.popleft()
for neigh_v in graph[cur_v]:
if neigh_v not in conn and neigh_v not in used:
queue.append(neigh_v)
used.add(neigh_v)
disconnected += users[neigh_v]
return disconnected
Feb. 22, 2019
