GeeksForGeeks: 조합 찾기(자바)

문제 연결

GeeksForGeeks: 조합 찾기 (클릭)

문제 요약

아래 두 가지 방법을 완료하십시오.

1. Union: 두 개의 하위 집합을 하나로 병합
2. isConnected: 두 하위 집합이 하위 집합인지 여부에 따라 true 또는 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: 쿼리 수