Disjoint Set(서로소 집합)

서로소 집합에 대한 연산

 

makeSet(v)

유일한 노드 v를 포함하는 새로운 집합을 생성하는 연산입니다

 

왜 -1로 초기화 시키는 걸까?

index는 음수가 될 수 없기 때문에 편하게 나타내기 위해 음수로 나타냅니다.

그리고 음수는 해당 집합의 "대표자"를 나타내게 됩니다.

 

 

findSet(v)

v를 포함하는 집합을 찾는 연산입니다. 즉, 대표자를 찾는 연산이라고 생각하시면 됩니다.

 

unionSet(u, v)

u와 v를 포함하는 두 집합을 "통합"하는 연산, 즉, "대표자"를 같게 해줍니다

v를 포함한 집합의 대표자는 u를 포함하는 집합의 대표자를 가르키게 됩니다

 

해당 연산들은 나중에 "최소 신장 트리"를 구하는데 필요한 자료구조입니다

 

코드

 

static int parent[] = new int[6];

public static void main(String[] args){

    //makeSet 부분
    Arrays.fill(parent, -1);
}

static int findSet(int v) {
    if(parent[v] < 0) return v;
    return findSet(parent[v]);

    /*parent[v] = findset(parent[v]);
    return parent[v];*/
}

static void unionSet(int u, int v) {
    u = findSet(u);
    v = findSet(v);
    if(u == v) return;
    parent[u] += parent[v];
    parent[v] = u;
    //큰 쪽을 루트로 둔다?? 사용자 마음
}
static int getSize(int v) {
    return -parent[findSet(v)];
}