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

대표적인 Union&&Find 문제이다.

 

0이 들어오면 a의 집합과 b의 집합을 Union 해준다.

1이 들어오면 a와 b가 같은 집합에 속해있는지 확인한다.

if (num == 0)
{
	Union(a, b);
}
else if (num == 1)
{
	if (Find(a) == Find(b))
	{
		cout << "YES" << '\n';
	}
	else
	{
		cout << "NO" << '\n';
	}
}

 

Union은 어떻게 하느냐?

일단 Find(a), Find(b)를 해서 a와 b의 대표노드들을 찾는다.

그리고 대표노드 하나를 선택해서 다른 대표노드의 자식으로 넣는다.

a가 b의 자식이 되거나 b가 a의 자식이 되거나.

나는 index가 큰 놈을 자식으로 만들고 index가 작은놈을 부모로 만들었다.

 

Find는 어떻게 하느냐?

우선 자신의 부모노드를 저장하기 위해 1차원 배열을 선언한다.

이 배열을 부모노드의 값을 저장하기 위해 사용된다.

만약 arr[3]=1이면 3의 부모는 1이라는 뜻이다.

Find는 자기 자신이 부모가 될 때까지 재귀함수를 통해 탐색하는 것이다.

만약 자기 자신이 부모이면 자기 자신을 return 해준다.

그리고 시간복잡도를 줄이기 위해 *경로축약*을 사용해 준다.

경로축약이란 Find작업을 거쳐간 노드들의 값을 대푯값으로 수정하는 것이다.

경로축약을 통해 Find 작업의 시간복잡도를 O(1)로 만들 수 있다. 굉장히 빨라진다.

 

Union && Find

Union && Find

 

#include <iostream>

using namespace std;
int arr[1000001];
int Find(int a);
void Union(int a, int b);
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m = 0;
	cin >> n >> m;
	for (int i = 0; i <= n; i++)
	{
		arr[i] = i;
	}
	for (int i = 0; i < m; i++)
	{
		int num = 0;
		int a = 0;
		int b = 0;
		cin >> num >> a >> b;
		if (num == 0)
		{
			Union(a, b);
		}
		else if (num == 1)
		{
			if (Find(a) == Find(b))
			{
				cout << "YES" << '\n';
			}
			else
			{
				cout << "NO" << '\n';
			}
		}
	}

	return 0;
}

int Find(int a)
{
	if (arr[a] == a)
	{
		return a;
	}
	else
	{
		arr[a]=Find(arr[a]);
	}
	return arr[a];
}
void Union(int a, int b)
{
	int num1 = Find(a);
	int num2 = Find(b);
	if (num1 < num2)
	{
		arr[num2]=num1;
	}
	else
	{
		arr[num1] = num2;
	}
}

Union을 하면서 주의할 점은 하나의 대표노드를 다른 대표노드의 자식으로 넣는 것이다.

arr[b]=num1; 이런식으로 작성하는 것을 주의하자.(대장을 옮겨줘야 한다. arr[num2]=num1)