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

문제 링크: https://www.acmicpc.net/problem/1717

 

서로소 집합을 쓰는 기초 문제입니다. 정말 union, find 연산만 그대~로 해주면 됩니다.

직전 게시물에 유니온 파인드에 대한 설명과 구현방법을 적어놨으니 참고하세요.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


vector<int> parent, ranks;

void init(int sz) {
	parent.resize(sz);
	for (int i = 0; i < sz; ++i)
		parent[i] = i;
	ranks = vector<int>(sz, 1);
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;	//같은 트리
	
	if (ranks[u] > ranks[v]) swap(u, v);

	parent[u] = v;

	if (ranks[u] == ranks[v]) ++ranks[v];
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	init(n+1);
	for (int i = 0; i < m; ++i) {
		int c, a, b;
		cin >> c >> a >> b;

		if (c == 0) {
			merge(a, b);
		}
		else {
			cout << (find(a) == find(b)?"YES":"NO") << '\n';
		}
	}

	

	return 0;
}

집합이 {0}, {1}, ..., {n} 이렇게 n+1개 있다는 점을 참고해주세요.