Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Power Supply by _Chico_
from collections import defaultdict
from collections import deque
from itertools import chain
def create_graph(network):
graph = defaultdict(list)
for i in network:
graph[i[0]].append(i[1])
graph[i[1]].append(i[0])
return graph
def BFS(graph, start, max_length):
queue = deque([([start], start)])
results=[]
visited = []
while queue:
path, current = queue.popleft()
# check if path has max_length
if len(path) == max_length:
results = results + path
visited.append(current)
for neighbor in graph[current]:
if neighbor in visited: continue
queue.append((path+[neighbor], neighbor))
return set(results)
def power_supply(network, power_plants):
#get set of all nodes
all_nodes = set(chain.from_iterable(network))
graph = create_graph(network)
if len(power_plants) == 0:
return all_nodes
else:
for i in power_plants:
all_nodes = all_nodes - BFS(graph, i, power_plants[i]+1)
#check if all nodes can be reached, if yes return empty list
if all_nodes == set(chain.from_iterable(network)):
return []
#report list of nodes that can't be reached
else:
return list(all_nodes)
July 10, 2021
