합집합 찾기(Union-Find)

 

서로소 집합 알고리즘 : 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별.

 

(1) 자기 자신을 부모로 가진다.

(2) A,B가 연결되어 있을 때 더 작은 값을 부모로 합친다 (Union)

(3) A,B,C가 연결되어 있을 때 재귀함수를 이용해서 가장 작은 값인 A로 부모를 지정한다.(Union-Find)

 

Find 알고리즘 : 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘.

 

 

 

 

Union-Find는 최소 비용 신장 트리를 만들기 위한 알고리즘인 Kruskal 알고리즘에 주로 사용됨.

 

//부모 노드를 찾는 함수 

int getParent(int parent[], int x){

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

    return parent[x] = getParent(parent, parent[x]);

}

//두 부모 노드를 합치는 함수

int unionParent(int parent[], int a, int b){

    a = getParent(parent, a);
    b = getParent(parent, b);

    if(a < b) parent[b] = a;
    else parent[a] = b;

}

// 같은 부모를 가지는지 확인

int findParent(int parent[], int a, int b){

    a = getParent(parent, a);
    b = getParent(parent, b);

    if(a==b) return 1;

    return 0;

}