여러분의 다리가 되어 드리겠습니다!

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	2632	1332	1041	51.791%

문제

선린월드에는 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

출처

High School > 선린인터넷고등학교 > 제3회 천하제일 코딩대회 D번

• 문제를 만든 사람: jh05013

알고리즘 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합

---

접근 방법

통과된 코드

#include <iostream>

using namespace std;

constexpr int MAX = 300001;

int N, v, u;

int parent[MAX];

void MakeSet(int n)
{
	for (int i = 1; i <= n; i++)  parent[i] = i;
}

int Find(int x) {

	if (parent[x] != x) parent[x] = Find(parent[x]); // Path compression

	return parent[x];
}

void Unite(int x, int y) {
	int rootX = Find(x);
	int rootY = Find(y);
	parent[rootY] = rootX; // Make rootX the parent of rootY
}

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	MakeSet(N);
	for (int i = 0; i < N - 2; i++) {
		cin >> v >> u;
		Unite(v, u);
	}

	int first, second = -1;
	first = Find(1);
	for (int i = 2; i <= N; i++) {
		if (Find(i) != first) {
			second = Find(i);
			break;
		}
	}

	cout << first << " " << second;

	return 0;
}