Disjoint Set은 Kruskal 최소 스패닝 트리에서 사용되는 데이터 구조입니다.
이 데이터 구조를 사용하면 두 개 이상의 노드의 합집합을 만들 수 있습니다.
이를 통해 두 노드가 not 그래프의 동일한 구성 요소에 속하는지 확인할 수 있습니다.
시간 복잡도는 O(4alpha)입니다(경로 압축을 사용하는 경우 그렇지 않으면 대수가 됩니다). 이는 입증된 일정한 시간 복잡도입니다.

자세한 내용은
를 참조하세요.

class Main{
    int parent[]  = new int[100000];
    int rank[] = new int[100000];
    void makeSet(){
        for(int i=1;i6->4->3 , here 3 is the parent of this union, so in order to get the parent of 7 which is 3 we can path compress it. like 7->3,6->3,4->3 etc.
    }
    void union(int u, int v){
        u = findParent(u);
        v = findParent(v);
        if(rank[u]  rank[v]) parent[v] = u;
        else parent[u] =v; // or parent[v] = u;
        // here u and v had the same rank
        //and now v became parent of u hence its rank will increase
        rank[v]  ;
    }

    public static void main(String args[]) throws Exception{
        Main m = new Main();
        //if we where given no of nodes as n
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        while(n>0){
            int u = n--;
            int v = n--;
            m.union(u,v);// this will create union of n nodes
        }
        // if 2 and 3 belong to the same component or not find out
        if(findParent(2)! = findParent(3)) System.out.println("Different component");
        else System.out.println("Same component");
    }
}