GeeksForGeeks : Union-Find (Java)

문제 링크

GeeksForGeeks : Union-Find (Click)

문제 요약

아래 2개의 메서드를 완성하라.

1. Union : 2개의 부분집합을 하나로 합치기
2. isConnected : 2개의 부분 집합이 하나의 부분 집합인지 true or false로 출력하기

문제 풀이

class Solution
{
    public int find(int x, int par[]) {
        while(x != par[x]) {
            x = par[x];
        }
        return x;
    }

    //Function to merge two nodes a and b.
    public void union_(int a, int b, int par[], int rank[])
    {
        a = find(a, par);
        b = find(b, par);

        if(a==b) return;

        if(rank[a] >= rank[b]) {
            rank[a] += rank[b];
            par[b] = a;
        } else {
            rank[b] += rank[a];
            par[b] = a;
        }
        return;
    }

    //Function to check whether 2 nodes are connected or not.
    public Boolean isConnected(int a, int b, int par[], int rank[])
    {
        a = find(a, par);
        b = find(b, par);

        if(a==b) return true;
        else return false;
    }

}

전형적인 Union-Find 알고리즘.
구글링을하면 Union-Find 알고리즘에 대한 쉬운 설명이 나오는데, 개념을 숙지하고 위의 기본 공식을 외우면
유사한 문제는 어렵지 않게 풀 수 있다.

시간복잡도

O(N+Q)

N : 노드의 개수
Q : 쿼리의 개수