서로소 집합 알고리즘

서로소 집합

• 수학에서 '서로소 집합'이란 공통 원소가 없는 집합을 의미한다.
• 트리 자료구조를 이용하여 집합을 표현한다.
• 연관되어있는 노드들을 서로 다른 집합으로 묶는 알고리즘이다.

트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1. A와 B의 루트 노드 A', B'를 각각 찾는다.
   2. A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)
2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

public static int v, e; //노드의 갯수와 간선의 갯수
public static int[] parent = new int[100001];   //부모 테이블 생성

//특정 원소가 속한 집합을 찾기
public static int findParent(int x){
    //자기 자신이 부모라면 자기자신 반환
    if(x == parent[x]) return x;
    //아니라면 자신의 부모를 호출
    return parent[x] = findParent(parent[x]);   //경로 압축 기법
}

//두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    //자신보다 작은 요소를 부모로 설정
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    //노드의 갯수와 간선의 갯수 입력받기
    v = sc.nextInt();
    e = sc.nextInt();
    //부모 테이블에서 부모를 자기 자신으로 초기화
    for(int i = 1; i <= v; i++){
        parent[i] = i;
    }
    //Union 연산을 각각 수행
    for(int i = 0; i < e; i++){
        //연결관계 인력받기
        int a = sc.nextInt();
        int b = sc.nextInt();
        unionParent(a, b);
    }

    //각 원소가 속합 집합 출력
    for(int i = 1; i <= v; i++){
        System.out.print(findParent(i) + " ");
    }
    System.out.println();
    //부모 테이블 출력
    for(int i = 1; i <= v; i++){
        System.out.print(parent[i] + " ");
    }

}