[자료구조](24)[서로소 집합 구현]

따로 삽입, 삭제가 필요하진 않으므로,

기존의 linked list로 트리를 구현하는게 아니라 배열로 구현한다!
-> 빠르고 가벼움

 

기본 골조

인덱스 i의 부모를 저장하는 parent 배열과
어떤 집합의 rank를 저장하는 rank 배열을 가지고 구현한다
    rank는 root일때만 쓰이므로 그것만 잘 업뎃해주면 됨

#define MAX_SIZE 10000

int parent[MAX_SIZE];
int rank[MAX_SIZE];

//자기 자신만 원소로 갖는 트리 생성
void init_set(int n){
    for (int i = 0; i < n; i++){
        parent[i] = i;
        rank[i] = 0;
    }
}

 

find

최대 O(n)으로 재귀적으로 root를 찾는다.

int find(int x){
    if (parent[x] != x){ //대표 노드가 나올때까지 탐색
        parent[x] = find(parent[x]); //path compression
                                     // 재귀적으로 올라가며 root를 찾고
                                     // 그 값을 parent[x]에 저장
    }
    return parent[x];
}

 

union

rank 기준으로 어떤 집합의 root의 부모가 다른 집합의 root로 설정하면 된다.
O(n)으로 합칠 수 있다

void union(int x, int y){
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY){ return; } //둘이 같은 집합이면 그냥 넘어감
    else if (rank[rootX] < rank[rootY]){
        parent[rootY] = rootX;
    }
    else if (rank[rootX] > rank[rootY]){
        parent[rootX] = rootY;
    }
    else {                        //둘이 랭크가 같다면
        parent[rootY] = rootX;    //X기준으로 합치고
        rank[rootX]++             //X의 랭크를 +1로 업데이트
    }
}