서로소

서로소 집합(Disjoint-set)

📔 서로소 집합(Disjoint-set) 이란 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들( 교집합이 없는 상태 ) 집합에 속한 하나의 특정 원소를 통해 각각의 집합들을 구분 ( 이를 대표자라고 함 ) 상호 배타 집합을 표현하는 방법 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표로 한다 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 트리 하나의 집합을 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 make_set(x) find_set(x) union(x,y) 📔 서로소 집합(Disjoint-set) 구현 def make_set(x): p[x] = x def find_set(x):..