disjoint set union 프로그래밍

출처: https://codeaccepted.wordpress.com/2014/05/27/disjoint-set-union/

#include<stdio.h>

int findParent(int i,int parent[]) {

//function to find the connected component that the ith node belongs to

    if(parent[parent[i]]!=parent[i])

        parent[i]=findParent(parent[i],parent);

    return parent[i];

}

void unionNodes(int a, int b, int parent[], int size[]) {

//to merge the connected components of nodes a and b

    int parent_a=findParent(a,parent);

    int parent_b=findParent(b,parent);

    if(parent_a==parent_b) return;

    //the larger connected component eats up the smaller one

    if(size[parent_a]>=size[parent_b]) {

         size[parent_a]+=size[parent_b];

         parent[parent_b]=parent_a;

    } else {

         size[parent_b]+=size[parent_a];

         parent[parent_a]=parent_b;

    }

    return;

}

 

int main() {

 

    int N,M,i,a,b;

    scanf(" %d %d",&N,&M);

    int parent[30001]={0};

    int size[30001]={0};

    int nos=0, max=0;

    for(i=1;i<=N;i++) {

        parent[i]=i;

        size[i]=1;

    }

 

    for(i=1;i<=M;i++) {

        //scan each edge and merge the connected components of the two nodes

        scanf("%d %d",&a, &b);

        unionNodes(a, b, parent, size);

    }

 

    //for(i=1;i<=N;i++) {

    //    printf("Node %d belongs to connected component %d\n",i,findParent(i,parent));

    //}

    for(i=1;i<=N;i++) {

        //this condition is true only for disjoint connected components

        if(findParent(i,parent)==i) {

            // printf("%d leader %d size\n", i, size[i]);

            if(size[i]>max) {

                max=size[i];

            }

            nos++;

        }

    }

    // printf("Total connected components : %d",nos);

    printf("%d\n", max);

 

    return 0;

}