[Algorithm] Union-Find

- Disjoint-Sets (서로소 집합들)

교집합이 존재하지 않는 집합

 

 

- UnionFind 로 해결 가능한 문제 

- 특정 집합에 몇 개의 원소가 속해있는지

- 특정 원소가 같은 집합에 속해있는지

https://www.acmicpc.net/problem/10775

https://www.acmicpc.net/problem/1717

 

 

- Union 연산과 Find 연산

1.

union(A, B) : B가 A의 밑으로 들어감, A와 B가 같은 조직이됨.

find(B) : B의 최상위 부모를 찾음 = A

2.

union(C, D) : D가 C의 밑으로 들어감, C와 D가 같은 조직이됨.

3.

union(D, B) : B가 D의 밑으로 들어감,

 

 

- UnionFind의 저장

각

 

 

- 코드 구현

#include <iostream>
using namespace std;
int arr[5];
void init()
{
    for (int i = 0; i < 5; ++i)
    {
        arr[i] = i;
    }
}
int find(int curr)
{
    if (curr == arr[curr]) return curr;
    int ret = find(arr[curr]);
    arr[curr] = ret;
    return ret;
}
void setUnion(int a, int b)
{
    int r1 = find(a);
    int r2 = find(b);
    if (r1 == r2) return;
    arr[r2] = r1;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    init();
    setUnion(0, 1);
    setUnion(2, 3);
    setUnion(0, 3);
    cout << find(3) << "\n";
    cout << find(4);
    return 0;
}

 

 

- UnionFind 응용

1. 그래프에서 싸이클 존재 유무 구하기

 

2. 독립적인 섬의 개수입력 값의 인접면이 땅인지 확인 하면서 섬의 개수를 계산.

4 입력 > 좌우 확인 > 없음 : 0+1 = 1

5 입력 > 좌우 확인 > 4와 합침 : 1+1 -1 = 1

7 입력 > 좌우 확인 > 없음 : 1+1 = 2

9 입력 > 좌우 확인 > 없음 : 2+1 = 3

8 입력 > 좌우 확인 > 7, 9 합침 : 3+1-2 = 2

6 입력 > 좌우 확인 > 4, 5 합침 : 2+1-2 = 1