합집합 찾기(Union-Find)

#include <stdio.h>

// 부모 노드를 찾는 함수
int getParent(int parent[], int x)
{
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
void 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;
}

int main(void)
{
    int parent[11];
    for (int i = 0; i <= 10; i++)
    {
        parent[i] = i;
    }
    unionParent(parent, 1, 2);
    unionParent(parent, 2, 3);
    unionParent(parent, 3, 4);
    unionParent(parent, 5, 6);
    unionParent(parent, 6, 7);
    unionParent(parent, 7, 8);
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
    unionParent(parent, 2, 8);
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
}

Union_Find란?

두 개의 노드를 선택해서 해당 노드가 서로 연결이 되어있는지 여부를 파악하기 위해 사용되는 알고리즘.

처음 그래프 상에서는 1번과 5번 노드가 연결되어 있지 않지만, unionParent함수에서 2번과 8번노드를 연결시켜 줌으로 써 그래프가 연결되어 1을 출력하도록 만들었다.