[백준/BOJ] 백준 1717번 : 집합의 표현

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

1717번: 집합의 표현

상호 배타적 집합을 유니온 파인드를 통해 표현한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> parent(1000001);
vector<int> rank_size(1000001);

//상호 배타적 집합을 유니온 파인드를 통해 표현한다

//유니온 파인드의 파인드
//node의 루트를 찾는다
int find(int node)
{
	int ret;

	if (node == parent[node])
		return node;

	else
		ret = find(parent[node]);

	return ret;
}

//유니온 파인드의 유니온
//node1의 집합과 node2의 집합을 합친다
void merge(int node1, int node2)
{
	node1 = find(node1);
	node2 = find(node2);

	//더 낮은 트리가 더 높은 트리에 포함되도록 더 낮은 트리를 더 높은 트리로 넣는다
	if (rank_size[node1] > rank_size[node2])
		parent[node2] = node1;

	else if(rank_size[node1] < rank_size[node2])
		parent[node1] = node2;

	else //rank_size[node1] == rank_size[node2] 일때 즉, 트리의 높이가 같다면 어떤 트리를 어떤 트리로 넣든 상관 없지만 이렇게 되면 높이는 커진다
	{
		parent[node1] = node2;
		rank_size[node2]++;
	}
}

void pre()
{
	for (int i = 0; i <= n; i++)
	{
		parent[i] = i;
		rank_size[i] = 0;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int zero_one, a, b;

	cin >> n >> m;

	pre();

	for (int i = 0; i < m; i++)
	{
		cin >> zero_one >> a >> b;

		if (zero_one == 0)
		{
			merge(a, b);
		}
		else if (zero_one == 1)
		{
			if (find(a) == find(b))
				cout << "YES" << "\n";
			else
				cout << "NO" << "\n";
		}
	}

	return 0;
}