Disjoint-set

Union-find라고도 불리는 서로소 집합 알고리즘으로 두 노드가 같은 집합에 있는지 여부를 판별할 수 있다

Disjoint-set 문제는 두 노드의 연결 상태를 주고 마지막에 여부를 묻는다

 

부모를 집합의 가장 작은 번호로 기입한 후 재귀적으로 두 노드를 탐색해서 부모를 알아내고 비교할 수 있다

 

int getparent(int idx) {

    if(parent[idx] == idx) return idx;

    else parent[idx] = getparent(parent[idx]);

}

 

void uniongroup(int a, int b) {
    int ap = parent(a);

    int bp = parent(b);

    if(ap < bp) parent[bp] = ap;

    else parent[ap] = bp;

}