Concept
disjoint set을 효과적으로 표현할 수 있는 트리형 자료구조
같은 set에 포함된 원소들은 같은 root를 가진다
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct _element {
struct _element *parent;
} Element;
Element *make_element() {
Element *element = (Element *)malloc(sizeof(Element));
element->parent = element;
return element;
}
Element *get_root(Element *element) {
Element *cur = element;
while(cur->parent != cur) {
cur = cur->parent;
}
element->parent = cur;
return cur;
}
int in_set(Element *e1, Element *e2) {
return get_root(e1) == get_root(e2);
}
void make_set(Element *e1, Element *e2) {
if(!in_set(e1, e2)) get_root(e1)->parent = e2;
}
int main() {
Element *e1 = make_element();
Element *e2 = make_element();
Element *e3 = make_element();
Element *e4 = make_element();
make_set(e1, e2);
make_set(e3, e2);
make_set(e4, e3);
printf("%d ", in_set(e1, e4));
return 0;
}