Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Node Disconnected Users by Rounin
def disconnected_users(net, users, source, crushes):
neighbours = dict()
crushed = dict()
nodes = dict()
for pair in net:
if not pair[0] in neighbours:
neighbours[pair[0]] = list()
if not pair[1] in neighbours:
neighbours[pair[1]] = list()
neighbours[pair[0]].append(pair[1])
neighbours[pair[1]].append(pair[0])
nodes[pair[0]] = True
nodes[pair[1]] = True
for crush in crushes:
crushed[crush] = True
connected = {} if source in crushed else {source: True}
nextnodes = [] if source in crushed else [source]
while len(nextnodes) > 0:
currentnode = nextnodes.pop()
if currentnode in connected:
for neighbour in neighbours[currentnode]:
if not neighbour in connected and not neighbour in crushes:
connected[neighbour] = True
nextnodes.append(neighbour)
victims = 0
for node in nodes:
if not node in connected:
victims += users[node]
return victims
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')
July 20, 2017