[백준][1717][C++] 집합의 표현

링크

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

1717번: 집합의 표현

해설

tree의 root를 이용해서 집합을 구별하는 문제입니다.

이 문제는 알면 쉬우나 모르면 발상을 해내는 것이 어려운 문제입니다.

 

처음에는 단순히 tree의 root를 계속 바꿔주면서 했더니 타임아웃이 났습니다.

그래서 root 를 찾을 때 찾아 올라가면서 들렸던 모든 수들의 현재 상위 노드 또한 root로 바꿔주었습니다.

 

알고리즘은 다음과 같습니다. ( a = 왼쪽 값 , b = 오른쪽 값)

입력이 0 일때

1. a의 root를 찾습니다.

2. b의 root 를 찾고 b의 root 를 a의 root로 연결시킵니다.

 (이때 각 root를 찾는 동안 들렸던 노드들의 상위 노드 또한 각자의 root로 갱신시켜줍니다.)

 

입력이 1 일 때

1. a의 root와 b의 root 가 같은지 확인합니다.

 

코드

#include <iostream>
using namespace std;

int N, M, TABLE[1000001];

int find_top(int _num) {
	if (TABLE[_num] == _num)
		return _num;
	return TABLE[_num] = find_top(TABLE[_num]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;

	for (int i = 0; i <= N; ++i)
		TABLE[i] = i;
	
	for (int i = 0; i < M; ++i) {
		int temp, a, b;
		cin >> temp >> a >> b;
		if (temp) {
			if (find_top(a) == find_top(b))
				cout << "YES" << "\n";
			else
				cout << "NO" << "\n";
		}
		else
			TABLE[find_top(b)] = find_top(a);
		
	}


	return 0;
}