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

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

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

 

유니온 파인드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int n;

vector<int> height;
vector<int> parent;

int GetParent(int a) {
	if (a == parent[a]) return a;
	return parent[a] = GetParent(parent[a]);
}

void Merge(int u, int v) {
	u = GetParent(u);
	v = GetParent(v);

	if (u == v) return;

	if (height[u] > height[v])
		::swap(u, v);

	parent[u] = v;

	if (height[u] == height[v])
		height[v]++;
}

int main()
{
	cin >> n;
	height = vector<int>(n + 1, 1);
	parent = vector<int>(n + 1);
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < n - 2; i++) {
		int s, e;
		cin >> s >> e;
		Merge(s, e);
	}
	int _parent = GetParent(1);
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		if (GetParent(i) != _parent) {
			ans = GetParent(i);
			break;
		}
	}
	cout << _parent << " " << ans;
}