(알고리즘) Disjoint Set 구조와 Union Find 알고리즘

//각 Edge의 정보가 담긴 struct이다.
struct Edge{
    int src, dest;
};

//각 Graph의 정보가 담긴 struct이다.
struct Graph{
    int V, E;
    struct Edge* edge;
};

//Graph를 생성해서 반환해주는 역할을 하는 함수이다.
//V는 vertex 개수, E는 edge의 개수를 의미한다.
struct Graph* createGraph(int V, int E){
    
    //그래프 공간 할당!
    struct Graph* graph = (struct Graph*) malloc( sizeof ( struct Graph));
    
    //그래프의 크기를 주어진 정보를 이용해 정해준다.
    graph->V = V;
    graph->E = E;
    
    //그래프의 edge 개수만큼 Edge의 공간을 할당해준다.
    graph->edge = (struct Edge*) malloc ( graph -> E * (struct Edge));
    
    //만든 그래프를 반환해준다.
    return graph;
}

//해당 vertex가 어느 집합에 속했는지 확인시켜주는 노드이다.
//두개의 vertex가 같은 집합에 있다면 find의 결과 값이 같을 것이다.
int find(int parent[], int i){

    //계속 타고 타고 가서 지금 parent가 없는 친구를 찾아보자(즉 그래프의 child node)
    if(parent[i] == -1) return i;
    return find(parent, parent[i]);
}

//만약 두개의 child node가 다르다면 두 노드를 이어줍시다. 하나의 그래프가 다른 그래프 밑으로 쏙 들어가게 된다.
void union(int parent[], int x, int y){

    //둘의 childnode를 찾고 다르면 하나가 다른 하나를 먹자.
    int xset = find(parent, x);
    int yset = find(parent, y);
    if(xset != yset){
        parent[xset] = yset;
    }
}

//Cycle을 확인해주는 함수
int isCycle(struct Graph* graph){

    //parent라는 어레이 변수를 생성하고 초기 값을 -1, 즉 부모가 없는 상태로 두자
    int *parent = (int*) malloc( graph->V * sizeof(int) ); 
    memset(parent, -1, sizeof(int) * graph->V); 
    
    //그래프의 Edge를 쭉 훑어봅시다.
    for(int i = 0; i < graph->E; ++i) 
    { 
        //Edge의 src와 dest node가 같은 graph에 속해있나 봅시다.
        int x = find(parent, graph->edge[i].src); 
        int y = find(parent, graph->edge[i].dest); 
        
        //같으면 Cycle이 있는겁니다.
        if (x == y) return 1; 
        
        //아니면 두 그래프를 합쳐요!
        Union(parent, x, y); 
    } 
    return 0; 
}

int main(){
    int V = 3, E = 3;
    struct Graph* graph = createGraph(V, E);

    // add edge 0-1 
    graph->edge[0].src = 0; 
    graph->edge[0].dest = 1; 

    // add edge 1-2 
    graph->edge[1].src = 1; 
    graph->edge[1].dest = 2; 

    // add edge 0-2 
    graph->edge[2].src = 0; 
    graph->edge[2].dest = 2;

    if(isCycle(graph)) printf("사이클 있어요~");
    else printf("사이클 없어요~");
}