union-find, disjoint set 간단 정리 서로소 집합을 표현할 수 있다. 트리 구조를 사용하며, 한 집합은 하나의 트리구조로 표현된다. 무방향 그래프의 사이클을 검사할 수 있다. 시간 복잡도는 대략 (find 연산의 수) x (log_2 노드의 개수) 이다. union 두 원소를 같은 집합으로 합치는 연산 원소 a, b와 둘의 루트 노드 A, B가 있을 때, A를 B의 자식으로 (혹은 반대로) 연결한다. def union(x, y): x = find_parent(x) y = find_parent(y) parents[x] = y find 원소의 부모를 찾는 연산 자식에서 부모 쪽으로 거슬러 올라간다. 노드의 부모가 자기 자신이 될 때까지(루트 노드) 반복한다. 경로 압축을 통해 최적화를 할 ..
