백준 1717번: 집합의 표현

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

1717번: 집합의 표현

 

 

0. 알고리즘 분류

 자료 구조, 분리 집합

 

 

1. 문제

 

 

2. 풀이

 유니온 파인드(Uniono-Find)를 이용하는 기본 문제이다. SCPC 1번문제가 유니온파인드를 사용한 문제였어서 공부했다. 개념 자체는 어렵지 않다. 두 집합을 합하는 union 연산과 부모를 찾는 find 연산 뿐이다.

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int p[1000001];

int find(int i) {
	if (p[i] < 0) {
		return i;
	}
	
	p[i] = find(p[i]);
	return p[i];
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	
	if (x == y) {
		return;
	}
	
	p[x] = y;
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	
	fill_n(p, n+1, -1);
	
	while (m--) {
		int op, x, y;
		scanf("%d %d %d", &op, &x, &y);
		
		if (op == 0) {
			merge(x, y);
		}
		else {
			x = find(x); y = find(y);
			if (x == y) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
	}
	
	return 0;
}