분리집합(유니온 파인드)

유니온 파인드 뼈대 코드

int parent[9];

int find(int x) {
    //부모노드 찾기
    if (parent[x] == x)//인덱스 값이 같다면 리턴
        return x;
    //인덱스 값 리턴
    return parent[x] = find(parent[x]);
}

///유니온 파인드 뼈대 코드
void merge(int x, int y) {
    //두 집합을 합치는 기능
    x = find(x);
    y = find(y);
    if (x == y) return;
    parent[y] = x;
}

//두 집합이 서로 같은 집합인지 확인
bool isUnion(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)
        return true;
    return false;
}

• 집합성 문제
• https://www.acmicpc.net/problem/1717
• https://www.acmicpc.net/problem/1976
• https://www.acmicpc.net/problem/16562
• https://www.acmicpc.net/problem/18116
• https://www.acmicpc.net/problem/10775