홍시홍의 프로그래밍

1. 정의 컴퓨터 과학 분야 에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 출처 : 위키피디아 내 해석 : 묶음으로 되어있지 않은 집합을 찾아내는 것, 사이클이 없음 한 노드의 부모를 찾거나 두 노드가 한 집합이 되도록 합치거나. 2. 구현 1) find(x) : x의 부모를 찾는 함수 - 경로 압축 : 시간 복잡도 상수 복잡도를 가진다고 함. 2) Union(a,b) : a와 b를 연결하는 함수(한 쪽으로 연결시켜줌) - 한 쪽으로 연결 시켜주는것이 헷갈리지 않음 ( 작은 쪽 or 큰 쪽) 3. 시간 복잡도 ..