백준 온라인 저지, 분리집합 / 17352번: 여러분의다리가되어드리겠습니다 (파이썬 / 백준 골드문제)

문제

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

"왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데...

입력

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

출력

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

제한

예제 입력 1

4
1 2
1 3

예제 출력 1

1 4

"4 1"이나 "2 4", "4 3" 등 가능한 정답은 많이 있지만, 아무거나 하나만 출력해야 한다.

예제 입력 2

2

예제 출력 2

1 2

예제 입력 3

5
1 2
2 3
4 5

예제 출력 3

3 4

힌트

접근 방법

- 분리집합을 통해 각 집합을 갱신하고, 집합에 포함되지 않는 섬과 집합에 포함되는 섬을 하나씩 출력한다.

코드

# https://www.acmicpc.net/problem/17352
# 접근방법
# 분리집합을 통해 각 집합을 갱신하고, 집합에 포함되지 않는 섬과 집합에 포함되는 섬을 하나씩 출력한다.
def get_parent(idx):
    if island[idx] == idx:
        return idx
    index = get_parent(island[idx])
    island[idx] = index
    return index

def find_union(i1, i2):
    x1 = get_parent(i1)
    x2 = get_parent(i2)
    if x1 < x2:
        island[x2] = x1
    else:
        island[x1] = x2


import sys
input = sys.stdin.readline

n = int(input())
island = [i for i in range(n+1)]
for _ in range(n-2):
    i1, i2 = map(int, input().split())
    find_union(i1, i2)

for i in range(1, n+1):
    if i == island[i]:
        island1 = i
for i in range(1, n+1):
    if i != island1:
        island2 = i
        break
print(island1, island2)