Concours Meilleur Dev : problème final

concours-meilleur-dev.py

import sys
from collections import deque

lines = []
for line in sys.stdin:
    lines.append(line.rstrip('\n'))
    
N = int(lines[0])
G = [set() for _ in range(N)]

for l in lines[1:]:
    u, v = map(int, l.split())
    local_print(str(u) + ' ' + str(v))
    if not (u==N or v==N):
        G[u].add(v)
        G[v].add(u)

weight = [1 for _ in range(N)]

Q = deque([u for u in range(N) if len(G[u])==1])

min_loss = N-1 # min loss at worst
already_seen = set()

while Q:
    u = Q.popleft()
    min_loss = min(min_loss, max(max((weight[v] for v in already_seen & G[u]), default=0), N-weight[u]))
    already_seen.add(u)
    for v in G[u]-already_seen:
        weight[v]+=weight[u]
        if len(G[v]-already_seen) <= 1:
            Q.append(v)

print(min_loss)