DisjointSets

package Z_Project;
 
import java.util.Arrays;
 
/*
 * 상호배타 집합 => MST(크루스칼 알고리즘에 활용)
 * 
 * makeSet(int x) 멤버 x를 포함하는 새로운 집합을 생성
 * findSet(int x) 멤버 x를 포함하는 집합의 대표자를 리턴
 * union(int x, int y) 멤버 x,y의 대표자를 구해서 두 집합을 통합
 * link(int px, int py) x의 대표자의 집합과 y의 대표자의 집합을 합침
 * 
 */
public class Z36_DisjointSets2 {
    public static int[] p = new int[10]; //부모를 저장할 배열
    public static int[] rank=new int[10];
    public static void main(String[] args) {
        
        for(int i = 0;i<p.length;i++) {
            makeSet(i);
        }
        
        printSet();
        union(0,1);printSet();
        union(2,3);printSet();
        union(0,3);printSet();
        
    }//end of main
    
    public static void printSet() {
        System.out.print("index : ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", i);
        }
        System.out.print("\nparent: ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", p[i]);
        }        
        
        System.out.println("\n");
    }
    
    
    /*멤버 x를 포함하는 새로운 집합을 생성*/
    public static void makeSet(int x) {
        p[x]=x; //부모 : 자신의 index로 표시 or -1
        //rank[x] = 0;//초기값 0임, 생략가능
    }
    
    /*멤버 x를 포함하는 집합의 대표자를 리턴*/
    public static int findSet(int x) {
        if(x==p[x]) return x;
        else {
            p[x]=findSet(p[x]); // Path Compression
            //rank[x]=1;//할 필요 없다. 대표자의 깊이(rank)만 알면된다.
            return p[x];
        }
    }
    
    public static void union(int x,int y) {
        int px = findSet(x);
        int py= findSet(y);
        
        // 서로 다른 집합일 경우만 합친다.
 
        if(px!=py) {
        //    p[py]=px; //대표자 합치기    
            link(px,py);
        }
    }
    
    /*x의 대표자의 집합과 y의 대표자의 집합을 합침, rank도 맞춤*/
    public static void link(int px, int py) {
        if(rank[px]>rank[py]) {
            p[py]=px; //작은쪽에 큰쪽을 붙인다.
        } else {
            p[px]=py;
            
            if(rank[px]==rank[py]) { //같은 경우는 rank 값이 증가
                rank[py]++;//집합의 대표자 랭크가 증가됨.
            }
        }
    }
}