DisjointSet

1. 정의, 설명��2. 데이터 표현��3. Union��4. Union – Rank Compression��5. Find – Path Compression�

Index

서로 공통된 원소를 가지고 있지 않은 두개 이상의 집합을 말한다.

​

DisjointSet data Structure를 사용하면 서로 다른 원소들이 어떤 집합에 속해 있는지를 판단하기에 유용하다.

​

-정의에 의해 Disjoint Set 사이에는 교집합이 없기 때문에, 합 연산을 하는 과정에서 두 집합 사이의 겹치는 원소를 특별히 고려하지 않고 모든 원소들을 하나의 집합으로 합치는 것이 가능하다. 이 합하는 과정과 각 원소들이 어떤 집합 속에 있는지 판별하는 과정을 효율적으로 찾기 해서 Disjoint Set Union을 사용합니다.

정의, 설명

데이터 표현

벡터를 이용하여 트리 구조를 표현

[5]

0

[1]

1

[1]

2

[3]

3

[3]

4

[3]

5

idx

Element

(parent idx)

1

2

3

4

5

0

그룹1

그룹2

Union

1

2

3

4

5

0

그룹1

그룹2

Merge(to : 그룹2 from : 그룹1) 호출

= >

1

2

3

4

5

0

그룹1

일반적으로 merge를 하게 되면 트리 형태가 유지 되지 않고 한쪽으로 치우치는 경우가 생길 수 있습니다.

Union – Rank Compression

1

2

3

4

5

0

그룹1

그룹2

Merge(그룹1, 그룹2) 호출 = >

높이(Rank)가 높은 그룹에 높이(Rank)가

낮은 그룹을 합칩니다.

일반적으로 merge를 하게 되면 트리 형태가 유지 되지 않고 한쪽으로 치우치는 경우가 생길 수 있습니다.

1

2

3

4

5

0

그룹2

Find->PathComprresson

1

2

3

4

5

u

그룹1

그룹2

1

2

3

4

5

u

그룹1

그룹2

Find(u) 호출 =>