Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for City's Happiness by Moff
from collections import defaultdict
def graph(net):
g = defaultdict(list)
for v1, v2 in net:
g[v1].append(v2)
g[v2].append(v1)
return g
def crush_subnetworks(g, users, crushed):
subnets = set()
visited = set()
for n in users:
if n == crushed or n in visited:
continue
subnet = {n}
queue = [n]
while queue:
x = queue.pop()
for v in g[x]:
if v not in subnet and v != crushed:
subnet.add(v)
queue.insert(0, v)
visited |= subnet
subnets.add(tuple(sorted(subnet)))
return subnets
def crush_happiness(g, users, crushed):
subnets = crush_subnetworks(g, users, crushed)
return sum(sum(users[v] for v in sn) ** 2 for sn in subnets) + users[crushed]
def most_crucial(net, users):
g = graph(net)
hp = {n: crush_happiness(g, users, n) for n in users}
min_h = min(hp.values())
return [k for k, v in hp.items() if v == min_h]
June 16, 2017
