Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Node Disconnected Users by Sim0000
from collections import deque
def disconnected_users(net, users, source, crushes):
net = [set(connection) for connection in net]
result = set.union(*net) # all unreachable node
seen = set()
q = deque([source])
# BFS
while q:
node = q.popleft()
if node in seen: continue # since already seen, skip this node
seen.add(node) # mark this node as seen
if node not in crushes:
result -= {node} # since reachable, remove this node
q.extend([(r - {node}).pop() for r in net if node in r]) # add all node next to the node
return sum(users[node] for node in result)
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert disconnected_users([
['A', 'B'],
['B', 'C'],
['C', 'D']
], {
'A': 10,
'B': 20,
'C': 30,
'D': 40
},
'A', ['C']) == 70, "First"
assert disconnected_users([
['A', 'B'],
['B', 'D'],
['A', 'C'],
['C', 'D']
], {
'A': 10,
'B': 0,
'C': 0,
'D': 40
},
'A', ['B']) == 0, "Second"
assert disconnected_users([
['A', 'B'],
['A', 'C'],
['A', 'D'],
['A', 'E'],
['A', 'F']
], {
'A': 10,
'B': 10,
'C': 10,
'D': 10,
'E': 10,
'F': 10
},
'C', ['A']) == 50, "Third"
print('Done. Try to check now. There are a lot of other tests')
April 27, 2017
Comments:
