BOJ - 집합의 표현(1717)

유니온 파인드(Union-Find)를 연습하기 위해 풀어본 문제입니다. 유니온 파인드는 배열을 사용해서 구현했습니다. 같은 집합에 포함되어 있는지 확인할 때는 find() 함수로 root노드가 같은지 확인하고, 합집합을 할 때는 각 트리의 root 노드가 다르다면 하나를 다른 노드의 자식으로 넣어서 트리를 합칩니다.

유니온 파인드

#define MAX 1000001
int p[MAX];

int find(int n) {
	if (p[n] < 0) return n;
	else {
		//경로 압축(path compression)
		p[n] = find(p[n]);
		return p[n];
	}
}

void uni(int a, int b) {
	int ap = find(a);
	int bp = find(b);
	if (ap != bp) {
		p[bp] = ap;
	}
}

메인 함수

#include <stdio.h>

int main() {

	// init
	for (int i = 0; i < MAX; i++) {
		p[i] = -1;
	};

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

	while(m--) {
		int op, a, b;
		scanf("%d %d %d", &op, &a, &b);

		if (op == 0) {
			uni(a, b);
		} else {
			int ap = find(a);
			int bp = find(b);

			if (ap == bp) printf("YES\n");
			else printf("NO\n");
		}
	}

	return 0;
}