1717 - 집합의 표현

기본적인 union find문제이다.

첫번째 풀이

#include <iostream>
using namespace std;
#define _CRT_SECURE_NO_WARNINGS

int K;
int n, m;
int parent[1000001];
int query, a, b;

int getParent(int x) {
	while (1) {
		if (parent[x] == x) { break; }
		x = parent[x];
	}
	return x;
}

void unionNode(int x, int y) { // x가 작은거, y가 큰거
	if (x > y) { int tmp = x; x = y; y = tmp; }
	parent[y] = x;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= 1000000; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &query, &a, &b);
		int x = getParent(a);
		int y = getParent(b);
		if (query == 0) {
			if (x!=y) {
				unionNode(x, y);
			}
		}
		else {
			if (x==y) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
		
	}
	return 0;
}

시간초과!
시간 줄일수 있는 방법을 전혀 모르겠어서 질문게시판을 봤는데 union-find에는 경로압축이라는 시간을 단축할 수 있는 방법이 있어서 그 방법을 적용한 후 문제를 해결할 수 있었다.

두번째 풀이

#include <iostream>
using namespace std;
#define _CRT_SECURE_NO_WARNINGS

int K;
int n, m;
int parent[1000001];
int query, a, b;

int getParent(int x) {
	if (x == parent[x]) {
		return x; // 루트일 경우 루트노드 return
	}
	else {
		int y = getParent(parent[x]);
		parent[x] = y; // 부모 노드를 최상단 루트로 바꿔줌
		return y;
	}
}

void unionNode(int x, int y) { // x가 작은거, y가 큰거
	if (x > y) { int tmp = x; x = y; y = tmp; }
	parent[y] = x;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= 1000000; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &query, &a, &b);
		int x = getParent(a);
		int y = getParent(b);
		if (query == 0) {
			if (x!=y) {
				unionNode(x, y);
			}
		}
		else {
			if (x==y) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
		
	}
	return 0;
}

문제 풀이 성공!

---

핵심

int getParent(int x) {
	if (x == parent[x]) {
		return x; // 루트일 경우 루트노드 return
	}
	else {
		int y = getParent(parent[x]);
		parent[x] = y; // 부모 노드를 최상단 루트로 바꿔줌
		return y;
	}
}

이 코드에서 else부분의 parent[x] = y;가 집합에 포함된 모든 노드들의 부모 노드를 최상단 루트로 바꿔주는 코드로 시간을 단축시킬 수 있는 포인트다. 그림으로 보면 이해가 쉽다.

int getParent(int x) {
	if (parent[x] == x) {
		return x;
	}
	else {
		return parent[x] = getParent(parent[x]); // 더 압축 가능
	}
}