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

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

---

UnionFind

 

+

1. UnionFind 최적화

2. 노드가 내림차순으로 들어올 때

3. 전체적으로 Root 갱신

---

---

• 제목

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

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

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

어제까지는 그랬다.

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

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

---

• 입력

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

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

---

• 출력

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

---

예제 입력1	예제 출력1
4 1 2 1 3	1 4

예제 입력2	예제 출력2
2	1 2

예제 입력3	예제 출력3
5 1 2 2 3 4 5	3 4

---

#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int root[300001];
int N, from, to;
void initRoot(int x){
	for(int n = 1 ; n <= x ; n++) root[n] = n;
}
int findRoot(int x){
	if(root[x] == x) return x;
	return root[x] = findRoot(root[x]); // optimization UnionFind
}
void unionRoot(int x, int y){
	if(x > y) swap(x, y); // set root as small order
	int rx = findRoot(x);
	int ry = findRoot(y);
	root[ry] = rx;
}
int main() {
    fastio;
    cin >> N;
    initRoot(N);
    for(int n = 0 ; n < N - 2 ; n++){
    	cin >> from >> to;
    	unionRoot(from, to);
	}
	int tmp = findRoot(1);
	for(int n = 2 ; n <= N ; n++){
		if(tmp != findRoot(n)){ // renew root
			cout << tmp << ' ' << root[n] << endl;
			break;
		}
	}
    return 0;
}