[백준][Python] 17352 여러분의 다리가 되어 드리겠습니다.

신장트리에서 마지막 하나의 간선을 그리는 방법으로 트리간 가중치가 존재하지 않기 때문에

간단한 union-find로 풀 수 있다.

 

import sys
input = sys.stdin.readline


def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]


def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        a, b = b, a
    parent[b] = a


N = int(input())
parent = {i: i for i in range(1, N+1)}
for _ in range(N-2):
    a, b = map(int, input().split())
    union(a, b)

pivot = find(1)
for i in range(2, N+1):
    if pivot != find(i):
        print(pivot, i)
        exit()