(알고리즘) 분리집합(Disjoint Set)

*분리집합: 교집합을 갖지 않는 집합들
즉, 서로 공통된 원소를 갖지 않는 집합

**분리집합에는 교집합이 있을 수 없다. 오직 합집합(Union)만 있을 뿐이다.



**분리집합의 표현**

-->자식이 부모를 가르킴
루트노드는 집합 그 자체이고, 루트노드 자신을 포함한 트리내의 모든 노드들은 그 집합에 속한다.

**집합의 구조체

typedef struct tagDisjointSet
{
struct tagDisjointSet* parent;
void* data;
}DisjointSet;


1) 합집합

void DS_Unionset(DisjointSet* Set1, DisjointSet* Set2)
{
Set2 = DS_FindSet(Set2);
Set2->parent = Set1;
}


2) 탐색

DisjointSet* DS_FindSet(DisjointSet* Set)
{
while (Set->parent != NULL)
{
Set = Set->parent;
}
return Set;
}