new_cities solution in Clear category for New Cities by dannedved
from itertools import chain
def subnetworks(net, crushes):
# Extract the number of unique nodes.
# This is the maximum amount of mayors we could possibly need (if all links are crushed).
total = len(set(chain(*net)))
# Iterater through the net and keep only those links that remain after the crushes.
after_crush = [link for link in net if not set(link) & set(crushes)]
# Create a new set to keep the track of remaining links throughout the next iteration.
linked = set()
# Iterate through the remaining links.
for rem_link in after_crush:
# Check if the link is redundant - i.e. if the two nodes are already connected in another way.
# The link is redundant if both the nodes have already been encountered and recorded in the "linked" set.
if not set(rem_link).issubset(linked):
# Update the "linked" set.
# For each non-redundant link, subtract 1 from the total amount of mayors.
total -= 1
# Finally, subtract one mayor for each destroyed node - they do not require much management.
return total - len(crushes)
Jan. 16, 2021