초기에 개의 집합 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
자료 구조
분리 집합
집합을 표현하는 유니온 파인드
로 푼 문제이다. 현재 노드를 n
이라고 하면, 부모 노드를 p[n]
으로 표현하였다. 또한 최상위 부모노드, 즉 루트노드에는 해당 집합의 크기가 절댓값인 음수로 넣어주어서 p[n]
이 0
미만인 경우에 n
번 노드가 루트 노드임을 명시했다.
find()
연산 시에도 현재 노드에서 부모 노드로 올라가는데, 올라가면서 방문하는 노드들도 루트로 연결하여 find()
연산의 최적화를 꾀했다.
merge()
의 경우 두 집합이 같은 집합인지 확인한 후에 병합해주었다. 병합 시에도 루트 노드로 삼은 노드의 값에 집합의 크기를 누적해주었다. 집합의 크기는 이 문제에서 이용하지 않았지만, 해당 기법이 있다는 것만 참고하면 된다.
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
int p[1000001];
int find(int n) {
if (p[n] < 0) return n;
p[n] = find(p[n]);
return p[n];
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
p[a] += p[b];
p[b] = a;
}
int main()
{
int n, m, in, a, b;
scanf("%d%d", &n, &m);
memset(p, -1, sizeof(int)*(n + 1));
while (m--) {
scanf("%d%d%d", &in, &a, &b);
if (in) {
if (find(a) == find(b)) printf("YES\n");
else printf("NO\n");
}
else merge(a, b);
}
return 0;
}