JUINTINATION

서로소 집합(Disjoint Set)이란? 공통 원소가 없는 두 집합, 즉 A∩B=∅을 만족시키는 두 집합 A, B를 서로소 집합이라고 한다. 유니온 파인드(Union-Find)란? 서로소 집합에 대한 연산을 할 때 사용하는 알고리즘이다. 쉬운 이해를 위해 다음의 예시를 보자. https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 위의 문제처럼 초기에 n+1개의 집합 {0}, {1}, {2}, ... , {n}이..