[알고리즘] Union-Find (유니온 파인드)

Union-Find (유니온 파인드)

 

 

 

1. Union-Find

- 합집합 찾기 알고리즘

- Disjoint-Set, 서로소 집합 이라고도 한다.

- 2개의 서로 다른 노드(x, y)를 선택했을 때, 2개의 노드가 같은 집합(그래프)에 속하는지 확인하는 알고리즘

 

 

 

2. Union

- 서로 다른 2개의 노드 x, y가 포함되어 있는 집합을 합치는 연산

 int find(int x) {
     if(x == parent[x]) return x;
     return parent[x] = find(parent[x]);
}

 

 

3. Find

- 노드 x가 어떤 집합에 포함되어 있는지 체크하는 연산. 루트 노드 반환.

void union(int x, int y) { // y > x
    x = find(x);
    y = find(y);
        
    // 부모가 다른 경우
    if(x != y) parent[y] = x;
}

 

 

4. 참고 문제

1) [백준] 집합의 표현

https://void2017.tistory.com/305

[백준] 1717 집합의 표현