[알고리즘] union find (disjoint-set)

Union find는
서로 중복되지 않는 부분 집합으로 나누어진 원소에 대하여 연결되어 있는 다른 원소를 찾거나 분리된 set을 합칠때 사용되는 알고리즘이다.

 

1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10

1번 항목은 해당 원소의 번호 2번 항목은 원소의 root의 번호를 나타내는 표가 있다.

 

위 그림처럼 나누어진 집합의 모음이 있다고 가정하자 그렇다면 위의 표는

1	2	3	4	5	6	7	8	9	10
1	1	1	2	2	6	6	6	9	9

이렇게 나타낼 수 있을 것이다. 이 표는 내 parent node의 원소를 나타내고 있지만 이 표만 봐서는 4 , 5와 같은 항목은 1과 연결되어 있는지 직관적으로 알기 힘들다.

그래서 모든 항목들을 해당하는 집합의 root 원소로 표현하는 것이다.
에를 들어 4 , 5번 원소가 연결되어 있는 2번 원소가 1번 원소와 연결되어 있기 때문에 4 , 5번 항목에 들어있는 2를 1로 수정하면 각 항목들은 root node인 1 , 6 , 9만 남게되고 2번 항목이 다르면 다른 set에 속한다고 알 수 있다.

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	6	6	6	9	9

 

구현 방법

1. 각 원소들을 1번 표와 같이 초기화 (각 원소가 하나의 집합)

2. 두 원소가 주어질 때, 이 원소의 집합을 하나로 합치는 union

3. 한 원소가 주어질 때, 이 원소가 포함되어 있는 집합을 반환하는 find

 

-업데이트 예정-

기본 코드 (재귀 스택 초과)
최적화 코드