개념

• Disjoint = 교집합이 공집합인 상황

연산

• make-set(u): u하나인 집합 하나 만들기
• find-set(u): u가 들어있는 집합의 root를 return
• union(u,v): 두집합을 합쳐주세요

구현

• p[u]: u번 요소의 부모의 Index를 return

코드

 static class Disjoint{
        int p[];
        public void makeSet(int u){
            p[u] = u;
        }
        public int findSet(int u){
            if(p[u]==u) return u;
            else return findSet(p[u]);
        }
        public void union(int u, int v){
            p[u] = findSet(v);
        }
    }

Union By Rank

• 트리높이를 줄이도록 union을 하는 방법
• union하려는 트리 각각을 따지고 작은게 큰거 아래로 들어가게한다.
• union을 할때 rank를 계산하자!

    static class Disjoint{
        int p[];
        int rank[];
        Disjoint(int n){
            p = new int[n];
            rank = new int[n];
        }
        public void makeSet(int u){
            p[u] = u;
            rank[u] = 0;
        }
        public int findSet(int u){
            if(p[u]==u) return u;
            else return findSet(p[u]);
        }
        public void union(int u, int v){
            //p[u] = findSet(v);
            u = findSet(u);
            v = findSet(v);
            if(rank[u] > rank[v]) p[v] = u;
            else {
                p[u] = v;
                if(rank[u]==rank[v]) rank[v]++;
                //어차피 disjoint set은 우너소 1개씩 있는 애끼리 합치는것으로부터
                //시작할테닏
            }
            
        }
    }