BaekJoon 1717번: 집합의 표현(C++)

www.acmicpc.net/problem/1717

1717번: 집합의 표현

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) Union Find 와 Disjoint set에 대한 이해가 필요한 문제이다.

Union Find

- 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미

- Tree 구조를 활용하여 parent를 찾아내는 find 함수와, 두 node의 parent가 같지 않을 때 트리를 합치는 merge함수로 구현한다.

2) 초기화 시에는 모든 parent 배열의 index를 자기 자신으로 초기화 한다.

3) find 함수는 자기 자신이 부모일때 까지 반복해서 root를 찾는다.

4) merge 함수는 두 노드의 부모가 같지 않은 경우 둘을 붙이는 역할을 한다.

#include <iostream>
#include <vector>

using namespace std;
int n, m;
int parent[1000001];
int find(int x)//x의 원소의 root 노드를 반환
{
	if (x == parent[x])
		return x;
	else
	{
		int p = find(parent[x]);//root를 찾는 재귀
		parent[x] = p;
		return p;
	}
}
void merge(int x, int y)
{
	x = find(x); //x의 root를 찾는다
	y = find(y); //y의 root를 찾는다

	if (x != y)//둘의 root가 다르면
		parent[y] = x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;//부모 배열을 자기 자신으로 초기화
	}
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 0)//합 시키는 경우
		{
			merge(b, c);
		}
		else//교집합 있는지 확인하는 경우
		{
			int b_parent = find(b);
			int c_parent = find(c);
			if (b_parent == c_parent)
				cout << "YES" << "\n";
			else
				cout << "NO" << "\n";
		}
	}
	
}