[백준 1717] 집합의 표현

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

1717번: 집합의 표현

 

요구사항

1. Union-Find 자료 구조 기본 문제

 

풀이

1. 기본 구현

 

시간 초과 주의(입출력이 printf, puts 사용 할 것)

 

#include <iostream>

using namespace std;

int parent[1000001];
int n, m;
int Find(int x)
{
	if (parent[x] == x)
		return x;
	else
		return parent[x] = Find(parent[x]);
}
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (x != y)
	{
		if (x < y)
			parent[y] = x;
		else
			parent[x] = y;
	}

}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int x, y, z;
	for (int i = 0; i <= n; i++)
		parent[i] = i;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y >> z;
		if (x == 0)
		{
			Union(y, z);
		}
		else if (x == 1)
		{
			int fy = Find(y);
			int fz = Find(z);
			if (fy == fz)
			{
				cout << "YES" << endl;
			}
				
			else
			{
				cout << "NO" << endl;
			}
		}
	}
}