Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
use 'New Cities' solution in Clear category for City's Happiness by kurosawa4434
from collections import defaultdict
from itertools import chain
def most_crucial(net, users):
def eval_subnetworks(node):
all_nodes = set()
cn_nodes = []
for n1, n2 in net:
all_nodes |= {n1, n2}
if not {n1, n2} & {node}:
for i, b in enumerate(cn_nodes):
if {n1, n2} & b:
cn_nodes[i] |= {n1, n2}
break
else:
cn_nodes.append({n1, n2})
ok = False
while not ok:
ok = True
for i, b1 in enumerate(cn_nodes):
for j, b2 in enumerate(cn_nodes[i+1:], start=i+1):
if set(b1) & set(b2):
cn_nodes[i] |= cn_nodes[j]
del cn_nodes[j]
ok = False
break
if not ok:
break
iso_nodes = all_nodes - set(chain(*cn_nodes)) - {node}
return (sum(users[i]**2 for i in iso_nodes)
+ sum(sum(users[c] for c in cn)**2 for cn in cn_nodes)
+ users[node])
happiness_dic = defaultdict(list)
for node in users:
happiness_dic[eval_subnetworks(node)].append(node)
return happiness_dic[min(happiness_dic.keys())]
May 1, 2017
