[BOJ 1717] 집합의 표현

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

1717번: 집합의 표현

---

위 문제는 n + 1개의 집합을 서로 합치고, 특정 원소가 같은 집합인지를 확인하는 문제이다.

 

이는 Union-Find 구조를 이용하면 쉽게 풀 수 있다.

 

---

#include <stdio.h>.

int n, m;
int t[1000001];

int find(int x)
{
	if (t[x] == x) return x;
	else return (t[x] = find(t[x]));
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	t[y] = x;
}

int main()
{
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++)
		t[i] = i;

	for (int i = 0; i < m; i++)
	{
		int o, a, b;
		scanf("%d%d%d", &o, &a, &b);
		if (o == 0)
			merge(a, b);
		else
		{
			if (find(a) == find(b))
				puts("YES");
			else
				puts("NO");
		}
	}
}