<백준> 1717

집합의 표현

문제
초기에
$n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.

입력
첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력
1로 시작하는 입력에 대해서
$a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는"yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

유니온 파인드를 알면 쉽게 해결할 수 있는 기본적인 문제인 것 같다.

vector<int> v;

int find(int a)
{
	if (a == v[a])
		return a;
	else
		return v[a] = find(v[a]);
}

void Union(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a != b)
		v[b] = a;
}

int Check(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a == b)
		return true;
	else
		return false;
}

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

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

	v.resize(n+1);

	for (int i = 0; i <= n; i++)
		v[i] = i;

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

		if (answer == 0)
			Union(a, b);
		else
		{
			if (Check(a, b))
				cout << "YES" << "\n";
			else
				cout << "NO" << "\n";
		}
	}
}