유니온 파인드 sample code

 Tree 의 최소 비용을 계산함에 있어 중복 tree 를 끊어주는 알고리즘 (최소비용신장 알고리즘에 있어서)

유니온 파인드


출처 : 
kks227.blog.me/220791837179


tree  를  search 하는 find and union 방식인데

시간이 오래 걸림으로 아래 알고리즘을 DP 를 살짝 가미해서 바꿔준다.


  int find(int n){

        if(p[n] < 0) return n;

        return find(p[n]);

    }

=>

 int find(int n){

        if(p[n] < 0) return n;

        p[n] = find(p[n]);

        return p[n];

    }

어차피 Tree 가 정해진 상태라 아래 처럼 그냥 해주면 된다.

void merge(int a, int b){

        a = find(a);

        b = find(b);

        p[a] = b;

        if(a == b) return;

}

어차피 부모가 정해진 두 a,b 값에 대해선 아래 처럼 활용이 가능하다.

void merge(int a, int b){         a = find(a);         b = find(b);         p[a] = b;         if(a == b) return;     }