Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
bfs solution in Clear category for Power Supply by EdinsonUwU
from copy import deepcopy
def power_supply(network, power_plants):
nodesConnections = {}
all_cities = []
for i in network:
for j in range(2):
if i[j] in nodesConnections.keys():
if j == 0:
nodesConnections[i[j]].append(i[1])
else:
nodesConnections[i[j]].append(i[0])
else:
if j == 0:
nodesConnections[i[j]] = [i[1]]
else:
nodesConnections[i[j]] = [i[0]]
if i[j] not in all_cities:
all_cities.append(i[j])
# iterative bfs algo
visited = [] # List to keep track of visited nodes.
queue = [] # Initialize a queue
def bfs(node, deep_path, current_deep=0):
graph = nodesConnections
visited = []
visited.append(node)
queue.append(node)
pops = 0
levelFinished = 1
children = 0
while queue and (current_deep < deep_path):
s = queue.pop(0)
for neighbour in graph[s]:
if neighbour not in visited:
children += 1
visited.append(neighbour)
queue.append(neighbour)
pops += 1
# to know where a new level has began
if pops == levelFinished:
current_deep += 1
levelFinished = deepcopy(children)
children = 0
pops = 0
return visited
for i in power_plants:
queue = []
visited += bfs(i,power_plants[i])
result = []
for i in all_cities:
if i not in visited:
result.append(i)
return set(result)
July 31, 2021
