[백준 1717] 집합의 표현

홍시홍 2020. 1. 2. 23:14

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

1717번: 집합의 표현

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

www.acmicpc.net

요구사항

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;
			}
		}
	}
}