서로소 집합 Disjoint set = 유니온 파인드 Union-find 수학에서 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로 union과 find 2개의 연산으로 조작한다. 시간복잡도 : O(V + M(1+log_(2-M/V) V)) 노드 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때, 경로 압축 방법을 적용한 시간복잡도 V = 1000, find/union 연산 100만 번일 때, 약 1,000만 번의 연산 필요 # 특정 원소가 속한 집합 찾기 def find_parent(parent, x) : # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 ..