Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS on colored (integers) networks (without a crash) for connected components solution in Clear category for City's Happiness by Phil15
def most_crucial(net, users):
all_happiness = [happiness(net, users, node) for node in users]
min_happiness = min(all_happiness)
return [node for node, happy in zip(users, all_happiness)
if happy == min_happiness]
def happiness(net, users, crush):
not_crashed_users = set(users) - {crush}
if not not_crashed_users:
return users[crush]
# G is the network graph without crashed node
G = {node: {user for user in not_crashed_users
if [node, user] in net or [user, node] in net}
for node in not_crashed_users}
# DFS on G with integer color for not crashed users
color = {user: 0 for user in not_crashed_users}
def dfs(s, n):
color[s] = n
for son in G[s]:
if not color[son]:
dfs(son, n)
i = 0
while 0 in color.values():
i += 1
user = next(user for user, int_color in color.items() if not int_color)
dfs(user, i)
N = max(color.values())
# There is N connected components (the maximum integer color).
# We apply happiness formula.
return users[crush] + sum(sum(nb for user, nb in users.items()
if user != crush
if color[user]==int_color)**2
for int_color in range(1, N+1))
Sept. 6, 2018