Tree(3) - Disjoint Set(분리 집합)

분리 집합이란 서로 공통된 원소를 갖지 않는 집합들을 말한다.

서로 구분되어야 하는 데이터 집합을 다룰 때 유용하다.

// gcc -o Test_DisjointSet.exe Test_DisjointSet.c DisjointSet.c; ./Test_DisjointSet.exe

#include <stdio.h>
#include <stdlib.h>

typedef struct tagDisjointSet
{
    struct tagDisjointSet* Parent;
    void*                  Data;
} DisjointSet;

void DS_UnionSet( DisjointSet* Set1, DisjointSet* Set2 )
{
    Set2 = DS_FindSet(Set2);
    Set2->Parent = Set1;
}

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

    return Set;
}

DisjointSet* DS_MakeSet( void* NewData )
{
    DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet));
    NewNode->Data   = NewData;
    NewNode->Parent = NULL;

    return NewNode;
}

void DS_DestroySet( DisjointSet* Set )
{
    free( Set );
}

int main( void )
{
	int a=1, b=2, c=3, d=4;
	DisjointSet* Set1 = DS_MakeSet(&a);
	DisjointSet* Set2 = DS_MakeSet(&b);
	DisjointSet* Set3 = DS_MakeSet(&c);
	DisjointSet* Set4 = DS_MakeSet(&d);

    printf("Set1 == Set2 : %d \n", DS_FindSet( Set1 ) == DS_FindSet( Set2 ) );

	DS_UnionSet( Set1, Set3 );
    printf("Set1 == Set3 : %d \n", DS_FindSet( Set1 ) == DS_FindSet( Set3 ) );

    DS_UnionSet( Set3, Set4 );
    printf("Set3 == Set4 : %d \n", DS_FindSet( Set3 ) == DS_FindSet( Set4 ) );

	return 0;
}