친구인가? (Disjoint-Set : Union&Find)

 

기존 배열

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

해당 인덱스의 값이 부모이다.

 

첫번째 Union(1, 2)

fa = Find(1) = 1, fb = Find(2) = 2 -- 1 != 2 이므로 unf[1] = 2

[0, 2, 2, 3, 4, 5, 6, 7, 8, 9]

 

두번째 Union(2, 3)

fa = Find(2) = 2, fb = Find(3) = 3 -- 2 != 3 이므로 unf[2] = 3 

[0, 2, 3, 3, 4, 5, 6, 7, 8, 9]

 

세번째 Union(3, 4)

fa = Find(3) = 3, fb = Find(4) = 4 -- 3 != 4 이므로 unf[3] = 4

[0, 2, 3, 4, 4, 5, 6, 7, 8, 9]

 

네번째 Union(1, 5)

return Find(unf[v]) 일 때

fa = Find(1) --> 1 != unf[1]

Find(unf[1]) = Find(2) -> Find(unf[2]) = Find(3) -> Find(unf[3]) = Find(4) -> return 4

fb = Find(5) = 5 

4 != 5 이므로 unf[4] = 5

[0, 2, 3, 4, 5, 5, 6, 7, 8, 9]

여기서는 1의 부모가 2, 2의 부모가 3, 3의 부모가 4, 4의 부모가 5

f(1)을 구하면 f(2)로 갔다가 f(3)으로 갔다가 f(4)로 갔다가 f(5)로 가서 5를 리턴받음

 

return unf[v]=Find(unf[v]) 일 때

fa = Find(1) --> 1 != unf[1]

unf[1] = Find(unf[1]) = Find(2)

unf[2] = Find(unf[2]) = Find(3)

unf[3] = Find(unf[3]) = Find(4)

unf[4] = Find(unf[4]) = return 4 

unf[3], unf[2], unf[1] 도 차례대로 4가 대입

fb = Find(5) = 5

4 != 5 이므로 unf[4] = 5;

[0, 4, 4, 4, 5, 5, 6, 7, 8, 9]

여기서는 1,2,3의 부모가 4, 4의 부모가 5

f(1)을 구하면 f(4)로 바로 가고 f(5)로 가서 5를 리턴 받음

f(1)=f(2)=f(3)=f(4)=f(5) 임!

 

이코테

if(fa!=fb) unf[fa]=fb; 조건 대신

if(fa >= fb) unf[fa]=fb;
else unf[fb] = fa; 가 들어가면

[0, 1, 1, 1, 1, 1, 6, 7, 8, 9] 로 바뀜

 

다섯번째 Union(6, 7)

 

여섯번째 Union(7, 8)

 

일곱번째 Union(3, 8)

 

 

 

import java.util.*;
class Main {
    //집합을 표현하는 배열
    static int[] unf;

    //부모 찾기
    public static int Find(int v){
        if(v==unf[v]) return v;
            //★★ufv[v]= 때문에 시간복잡도가 엄청나게 줄어들음
            //일자 트리에서 부모자식트리로 변경됨
        else return unf[v]=Find(unf[v]);
    }

    //합치기
    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb) unf[fa]=fb;
    }

    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();

        unf=new int[n+1];
        for(int i=1; i<=n; i++) unf[i]=i;

        for(int i=1; i<=m; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            //a,b를 한 집합으로 만들기
            Union(a, b);
            System.out.println(Arrays.toString(unf));
        }

        //친구 관계인지 확인하는 입력
        int a=kb.nextInt();
        int b=kb.nextInt();
        int fa=Find(a);
        int fb=Find(b);
        if(fa==fb) System.out.println("YES");
        else System.out.println("NO");
    }
}