[BOJ 17352] 여러분의 다리가 되어 드리겠습니다!

문제 링크 : https://www.acmicpc.net/problem/17352

문제

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

어제까지는 그랬다.

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

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

입력

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

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

출력

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

제한

시간 제한	메모리 제한
1sec	512MB

---

풀이

$N$개의 정점이 $N-1$개의 간선으로 연결된 트리 구조에서 간선 하나가 제거되어 두 개의 분리된 컴포넌트가 생긴 상황이다. 이 두 컴포넌트를 다시 하나로 합쳐 전체를 연결하기 위해 어떤 정점들이 서로 같은 그룹에 속해 있는지 판별해야 하므로, 분리 집합 자료구조를 활용한다.

해결 과정은 다음과 같다:

• 모든 정점에 대해 자기 자신을 부모로 갖는 분리 집합을 초기화한다.
• 주어지는 $N-2$개의 간선 정보를 읽으며 merge 연산을 수행하여 정점들을 그룹화한다.
• 모든 간선을 처리한 후에는 전체 그래프가 정확히 두 개의 집합으로 나뉘게 된다.
• 임의의 정점(예: 1번 정점)이 속한 집합의 루트를 찾는다.
• 나머지 모든 정점을 순회하며 1번 정점과 다른 루트를 가진 정점을 찾아 두 번호를 출력한다.

find 연산 시 경로 압축(Path Compression)을 적용하면 각 연산을 거의 상수 시간에 처리할 수 있다. 정점의 개수 $N$이 최대 $300\,000$이므로 전체 시간 복잡도는 다음과 같다:

\[O(N \alpha(N))\]

여기서 $\alpha$는 아커만 함수의 역함수로, 실제로는 상수와 다름없는 매우 작은 값을 가진다. 따라서 제한 시간 1초 내에 매우 여유롭게 해결 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 : 분리 집합