전력망을 둘로 나누기

best = -1 target = -1 from collections import defaultdict def dfs(u, A, vis): global best, target s = 1 for v in A[u]: if vis[v]: continue vis[v] = True res = dfs(v, A, vis) s += res if abs(res-target) < abs(best-target): best = res return s def solution(n, wires): global target target = n//2 A = defaultdict(list) for u, v in wires: A[u].append(v) A[v].append(u) vis = [False] * (n+1) dfs(1, A, vis) return abs(n - 2 * best)