백준 17352번 여러분의 다리가 되어 드리겠습니다! 문제풀이(C++)

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

아이디어

다른 두 섬을 다리로 이어서...

이어져있는 다리들을 하나로 묶어서 두개의 구역으로 나누고

다른 값이 나오는 두개의 다리를 찾는다

크루스칼 알고리즘 활용

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 300'000 + 10
int n;
int bridge[MAX];
int getParent(int x) {
	if (bridge[x] == x) return x;
	else return getParent(bridge[x]);
}
void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a > b) bridge[a] = b;
	else bridge[b] = a;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++)
		bridge[i] = i;
	for (int i = 0; i < n - 2; i++) {
		int start, end; cin >> start >> end;
		unionParent(start, end);
	}
	int tmp = getParent(1);
	for (int i = 2; i <= n; i++) {
		if (tmp != getParent(i)) {
			cout << tmp << ' ' << getParent(i) << '\n';
			break;
		}
	}
	return 0;
}