# Union-Find

- Union-Find를 알기 앞서, `Disjoint Set`이라는 것을 먼저 보면, disjoint set 은 **중복되지 않은 원소를 가진 두 집합**(서로소 집합)이라고 볼 수 있다.
- Union-Find 는 union 의 기능과 find 의 기능을 갖고 있는 자료구조라고 생각하면 된다. **union** 이 하는 기능은 두 원소를 하나의 집합으로 만드는 기능이고, **find** 는 특정 원소가 어느 집합에 속해있는지 알려주는 기능이다.

Union
---
- union(a,b) 는 원소 a 가 속한 집합과 원소 b 가 속한 집합을 합치는 과정이다.union 을 하는 과정은 다음과 같다
1. 원소 a 와 b의 root 를 찾는다. 각 원소의 root 를 찾아 이 두 root를 하나로 합치는 과정을 해야하므로 필요한 과정이다. 이 때, Find 기능을 사용한다. (Find의 내용은 아래에서 다룸)
2. A 와 B 의 root 중 작은 값을 A 와 B 의 공통 root 로 설정한다. 즉, 두 집합을 하나로 합치려면 공통의 root를 가져야 하는데 이 값을 작은 값으로 일반적으로 설정한다.
3. 모든 원소와 집합에 대해서 union 연산을 처리할 때까지 1과 2를 반복한다.

[Union](https://velog.io/@woo0_hooo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-union-find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

Find
---
- find(a) 하는 과정은 다음과 같다.
1. 원소 a의 부모가 자기 자신이 아니라면 (자신이 root 가 아니라면) find (parent[a]) 를 수행한다.
2. 자기 자신이 부모가 되면 재귀 호출은 멈춘다.
[Find](https://velog.io/@woo0_hooo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-union-find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

- 여기서 find 의 과정이 비효율적으로 느껴질 수 있다. 5 -> 4 -> 3-> 2-> 1 의 관계라고 하면, 5의 root를 찾는 일은 항상 $O(N)$ 만큼의 시간이 소요된다. union/find 연산이 $M$ 횟수만큼 반복된다고 하면, 시간복잡도는 $O(NM)$ 이 된다. 이 문제를 해결하기 위해서 압축된 경로를 사용하는 것이 좋다.
- 특별한 방법은 아니고, parent 를 저장하는 테이블에 root 를 저장하면 된다. 즉, 5의 부모는 4가 아니라 1을 저장하면 된다.

[Find2](https://velog.io/@woo0_hooo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-union-find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return parent[x]

활용 사례
---
- Union-Find는 그래프에서 $forest$를 찾기
- Kruskal's algorithm: Kruskal's algorithm 은 weight 이 가장 낮은 간선 순서대로 정렬해서 병합(union) 해나가는 방식으로 union-find 자료구조에 적합하다.
- 무방향 그래프에서의 Cycle을 판별
- 그래프가 Bipartite인지 판별
- 문제
- https://leetcode.com/problems/number-of-provinces/
- https://leetcode.com/problems/redundant-connection/