Union-find(Disjoint-set)
- Disjoint set : 서로 중복되지 않는 집합(서로소 집합)
- Union-find : disjoint set을 표현하기 위해 사용하는 알고리즘
Union-find의 메소드
- find(x) : x가 속한 집합의 대표값을 반환한다.
- union(x,y) : x가 속한 집합과 y가 속한 집합을 합친다.
구현 방법
1. 배열
- find(x) : O(1)
- union(x,y) : O(N)
2. 트리
- find(x) : O(트리의 높이)
- union(x,y) : < O(N)
관련 알고리즘 문제
https://www.acmicpc.net/problem/tag/Disjoint-set
Disjoint-set - 1 페이지
www.acmicpc.net
초심자용 추천 문제
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a
www.acmicpc.net
참고자료
- 구현 방법에 따른 장단점
https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
[알고리즘] Union-Find 알고리즘 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
'CNU 학습 동아리 > 2020 동계 학습 동아리' 카테고리의 다른 글
| 2020 동계 학습 동아리_6회차_2020-02-14(금) (0) | 2020.02.14 |
|---|---|
| 2020 동계 학습 동아리_5회차_2020-02-11(화) (0) | 2020.02.12 |
| 2020 동계 학습 동아리_4회차_2020-02-10(월) (0) | 2020.02.10 |
| 2020 동계 학습 동아리_2회차_2020-02-04(화) (0) | 2020.02.04 |
| 2020 동계 학습 동아리_1회차_2020-02-03(월) (0) | 2020.02.03 |
댓글