[Disjoint Set] 1717 집합의 표현

 

예제입력 및 출력)

7 8
0 1 3
0 3 2 3 4 5 6 7
1 1 7
NO
0 7 6
0 3 2 3 4 5 6 6
1 7 1
NO
0 3 7
0 3 2 6 4 5 6 6
0 4 2
0 3 2 6 2 5 6 6
0 1 1
0 6 2 6 2 5 6 6
1 1 1
YES

 

이 문제를 풀기 위해서는 Disjoint Set을 공부하면 좋습니다.

집합을 표현하고 다루는 3가지 함수를 배워봅시다.

 

Disjoint Set은 만드는 방법이 연결리스트와 트리가 있지만,

Union(합집합), Find 의 성능이 트리가 더 우월합니다.

 

자료구조는 트리로 가정해봅시다.

 

1. makeset()

 

{0}, {1}, {2}, ... , {n} 의 집합을 만들어봅시다.

p[n+1] 배열을 만들고, 

p[x] = x

라고 하면,

예를들어 p[1] = 1 이며, 이는 "1의 부모(parent)는 1이다."를 나타낼 수 있습니다.

즉, 각 집합의 대표 루트를 통해 집합의 이름을 표현하는 것입니다.

 

2. findset(a)

 

예를들어 2가 어떤 집합에 속하는 지를 찾아봅시다.

우리는 그 집합의 대표 루트를 구하면 됩니다.

구현 코드는 아래에 있습니다.

(재귀함수사용, while문으로도 가능)

 

3. unionset(a, b)

 

원소 a가 있는 집합과 원소 b가 있는 집합을 하나의 집합으로 합쳐봅시다.

즉 합집합 연산을 하는 것입니다.

이는 집합의 대표루트가 서로 다를 경우, (즉 원소 a와 b가 다른 집합에 있을 경우)

한 루트를 다른 루트에 이어 붙임으로써 p[b] = a (b의 부모가 a가 되도록 이음) 가능합니다.

 

------------------------------------------------------------------------------------------

여기서 find와 union 에서는 시간 속도의 성능을 증가시키기 위하여

각각 경로압축, rank 방법을 사용합니다.

 

#include <cstdio>

int p[1000002]; // parent
int rank[1000002];

void makeset(int n){
    for (int i=0; i<=n; ++i){
        p[i] = i;
    }
}

int findset(int x){
    if (x == p[x])
        return x;
    return p[x] = findset(p[x]); // 경로 압축: rank를 낮출 가능성이 커져 연산속도 빨라짐
    // return findset(p[x]); // 경로 압축 X
}

void unionset(int x, int y){
    // p[findset(y)] = findset(x); // without 'rank'
    int X = findset(x);
    int Y = findset(y);
    if (rank[X] > rank[Y]){
        p[Y] = X;
    }
    else {
        p[X] = Y;
        if (rank[X] == rank[Y]) rank[Y] = rank[X] + 1;
    }
}

int main() {
    int n, m, c, a, b;
    scanf("%d %d", &n, &m);
    makeset(n);
    while(m--){
        scanf("%d %d %d", &c, &a, &b);
        if (c == 0) {
            unionset(a, b);
        }
        else if (c == 1){
            if (findset(a) == findset(b)) printf("YES\n");
            else printf("NO\n");
        }
    }


    return 0;
}