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

여러분의 다리가 되어 드리겠습니다! (백준 Gold 5)

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

N개의 노드와 N-2개의 간선이 주어질때
간선을 하나 추가하여 전부 연결된 상태로 만드는 문제

풀이 방법

N-2 개를 기반으로 ‘분리 집합’을 적용하면 풀 수 있다

• 주어지는 N - 2 개의 데이터들을 Union
  
• 이후 i = 0, j = i + 1 로 반복문을 돌고
  Union이 성공한다면 해당 값들을 출력하고
  프로그램을 종료시킨다
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int FindParent(vector<int>& pv, int x)
{
	if (pv[x] == x)
		return x;

	return pv[x] = FindParent(pv, pv[x]);
}

bool Union(vector<int>& pv, int a, int b)
{
	a = FindParent(pv, a);
	b = FindParent(pv, b);

	if (a == b)
		return false;

	pv[a] = b;

	return true;
}


int main()
{
	int n;
	cin >> n;
	vector<int> pv(n);
	for (int i = 0; i < n; i++)
		pv[i] = i;

	for (int i = 0; i < n - 2; i++)
	{
		int t1, t2;
		cin >> t1 >> t2;
		t1--;
		t2--;
		Union(pv, t1, t2);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (Union(pv, i, j))
			{
				cout << i + 1 << " " << j + 1;
				return 0;
			}
		}
	}

	return 0;
}

결과