목록find (1)

소근소근

[알고리즘/자료구조] 분리 집합( Disjoint Set (a.k.a Union & Find) ) 코드 구현 C++ , 집합 크기 구하기

분리 집합이란 교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. 구분해야 하는 데이터 집합들을 다루는 알고리즘에서 사용할 수 있다. 분리집합에서는 자식 노드가 부모 노드를 가리키게 되어 있다. 보통 특정 집합의 대표 노드(루트)를 자식 노드들이 가리키고 있는 형태이다. 분리집합 연산에는 두 가지가 있다. 1. Union(x,y) 합집합 연산이다. 두개의 집합을 합치기 위해서 각 두 집합의 대표(루트)노드를 찾고, A의 대표노드의 부모를 B의 대표 노드로 설정한다. void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px != py) { parent[px] = py; set_size[py] += set_size[px]; } } 합치려고 ..
Algorithm 2022. 1. 5. 16:01
이전 Prev 1 Next 다음