[백준] 1717 집합의 표현

문제

초기에 �+1$n+1$개의 집합 {0},{1},{2},…,{�}$\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

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

출력

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

 

 

유니온 파인드 문제입니다.

a와 b를 합치면 a의 부모와 b의 부모중 작은값을 연결합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int n, m, r[1000001];
int p(int k) {
	return r[k] == k ? k : r[k]=p(r[k]); //주의 시간초과
}

void merge(int a, int b) {
	int A(p(a)), B(p(b));	
	A > B ? r[A] = B : r[B] = A;
}
void query(int a, int b) {
	p(a) == p(b) ? printf("YES\n") : printf("NO\n");
}
int main() {
	FAST;
	int x, a, b;
	cin >> n >> m;
	rep(i, n + 1)r[i] =	i;
	while (m--) {
		cin >> x >> a >> b;
		x == 0 ? merge(a, b) : query(a, b);
	}
}