[BOJ] 1717 집합의 표현

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

Note

0 ~ n 까지 총 n + 1개로 구성된 집합이 합 연산과 두 원소가 같은 집합에 속해 있는지 구하는 연산을 진행 할 때 같은 집합에 속하는지 확인 하는 연산에 대해서 결과 값을 출력해주어야 한다.

Dis-Joint Set에 대한 기초적인 문제, 추가로 위 문제에서는 높이를 최대 2로 낮추는 작업을 해주어야 시간제한에 걸리지 않는다.
합집합을 구하는 연산을 진행 할 때 부모를 찾는 작업을 진행 해야 하는데 그 과정에서 높이를 압축시키는 과정이 진행 된다.

스터디를 진행 하면서 푸는 문제이기에 Dis-Joint Set을 클래스화 시켜 문제를 해결했다.

소스코드

#include <iostream>
#include <vector>

using namespace std;

class DisJointSet
{
	int size;
	vector<int> parent;

public:
	DisJointSet(int size) : size(size) {
		parent.resize(size);
		for (int i = 0; i < size; i++) parent[i] = i;
	};

	int find(int v) {
		if (parent[v] == v) return v;
		
		return parent[v] = find(parent[v]);
	}
	bool merge(int x, int y) {

		int px = find(x);
		int py = find(y);

		if (px == py)
			return false;

		parent[px] = py;

		return true;
	}
};

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

	int n, m;

	cin >> n >> m;

	DisJointSet dis(n+1);

	while (m--)
	{
		int order, x, y;
		cin >> order >> x >> y;

		if (order) {
			if (dis.find(x) == dis.find(y))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
		else
		{
			dis.merge(x, y);
		}
	}

	return 0;
}

2019-02-13 02:02:18에 Tistory에서 작성되었습니다.