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

문제 링크: https://www.acmicpc.net/problem/17352

 

유니온 파인드 문제입니다.

입력대로 merge를 하면 섬들이 두 그룹으로 나뉩니다.

0번 섬의 루트를 저장한 뒤 이걸 나머지 섬 루트랑 비교했을 때 루트 인덱스가 다르면 다른 그룹에 들어있는 거니까 두 그룹의 루트를 이어주면 됩니다. 두 섬 자체를 이어줘도 되고요.

아무 방법으로 이으면 된다고 하니 적당히 이어주면 됩니다.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


vector<vector<int>> graph;

vector<int> parent;

void init(int n) {
	parent.resize(n);
	for (int i = 0; i < n; ++i)
		parent[i] = i;
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;

	parent[u] = v;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	init(n);
	
	int a, b;
	for (int i = 0; i < n - 2; ++i) {
		cin >> a >> b;
		--a, --b;
		merge(a, b);
	}

	int c = find(0);
	for (int i = 1; i < n; ++i) {
		int d = find(i);
		if (c != d) {
			cout << c + 1 << ' ' << d + 1 << '\n';
			break;
		}
	}

	return 0;
}