문제

https://www.acmicpc.net/problem/17352

---

입력

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

---

출력

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

---

풀이

제한조건

• (2 ≤ N ≤ 300,000)

접근방법

탐색, Disjoint Set

문제를 해결하기 위한 방법 2개가 떠올랐다.
1. 단순 탐색을 통해 분리된 그룹 찾기.
2. union find를 이용해서 찾기.

단순 탐색보다 disjoint set을 이용하는 방식이 코드 작성량이 작기 때문에
해당 방법으로 진행했다.

(https://velog.io/@hyeokkr/%EC%84%9C%EB%A1%9C%EC%86%8C-%EC%A7%91%ED%95%A9DisJoint-Set-Union-Find)

탐색과 달리 다리의 정보를 저장할 필요가 없다.
입력받는 즉시 union 함수를 이용해서 합쳐주자.

모든 다리의 순회가 종료된다면 parent가 다른 2개를 찾으면 정답이 된다.
이때, parent를 구하는 과정에서 경로 압축을 진행했지만, 입력 순서에 따라서 추가적인 갱신이 필요한 것들이 있을 수 있다.

이를 위해 한 번더 순회하며 find함수만 수행해주자.

해당 방법이 아니라 탐색으로 진행한다면 어떻게 할 수 있을지 생각해보자.
우선 DFS 또는 BFS로 탐색하기 위해서 다리의 정보를 모두 저장해주자.
그 다음 탐색을 시작하며 서로 다른 그룹을 찾고, 각 그룹의 2개를 뽑아주면 된다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static int[] parent;
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader((System.in)));

		N = stoi(in.readLine());
		parent = new int[N + 1];
		for (int i = 1; i <= N; ++i)
			parent[i] = i;

		for (int i = 0; i < N - 2; ++i) {
			String[] inputs = in.readLine().split(" ");
			union(stoi(inputs[0]), stoi(inputs[1]));
		}

		for (int i = 1; i <= N; ++i)
			find(i);

		StringBuilder sb = new StringBuilder();
		int base = parent[1];
		int other = Arrays.stream(parent).filter(e -> e != base && e != 0).findFirst().getAsInt();
		sb.append("1").append(" ").append(other);
		System.out.println(sb);
	}

	public static int find(int n) {
		if (parent[n] == n)
			return n;
		return parent[n] = find(parent[n]);
	}

	public static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b)
			return;

		if (a <= b) {
			parent[b] = a;
		} else {
			parent[a] = b;
		}
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}