union-find

union : 특정한 2개의 노드를 연결해 1개의 집합으로 묶음

find : 두 노드가 같은 집합에 속해 있는지 체크

 

1차원 배열을 이용

index = 값

value = 대표 노드(집합)

 

find :4 index와 value 가 동일한지 확인한다

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

 

 

// find
public static void find(int a) {
    if (a = label[a])
        return a;
    else return label[a] = find(label[a]);
}

 

 

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