Union & Find 재귀 설정 오류

두 원소 그룹의 대표노드끼리 연결하는 것은 상관 없지만, 그룹 내부의 모든 원소가 연결되어있는 것을 설정해줘야할 필요가 있을 때 신경을 써 줘야함.

find

    static int find(int n){
        if(n == rooted[n]){
            return n;
        }else{
            return rooted[n] = find(rooted[n]);
        }
    }

두 그룹의 대표 노드끼리 연결

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            rooted[b] = a;
        }
    }

두 그룹간의 모든 노드가 대표노드를 똑같이 가지게함.

   static void union(int a, int b){
        int fa = find(a);
        int fb = find(b);
        if(a != b){
            for(int i = 0; i<n; i++){
                if(rooted[i] == fb){
                    rooted[i] = fa;
                }
            }
        }
    }

checkSame

모든 인덱스를 탐색해야하고, 해당 건수가 많다면 비효율적임..
이를 통해서 같은 부모 노드를 가지는지 확인하기 위해
find를 한번 더 호출해서 최종 부모 노드까지 재귀탐색 할 수 있도록 확인

    static boolean checkSame(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b){
            return true;
        }
        else{
            return false;
        }
    }