서로소 집합, 크루스칼, 위상 정렬

서로소 집합(disjoint set)

union, find연산을 가지는 자료구조로 최상단의 부모노드가 서로 다르면
다른 집합으로 보는 트리형 자료구조로 생각할 수있다.

구현은 트리형으로 하지 않고 노드갯수와 같은 크기의 parent배열을 이용하여
일종의 linked list 처럼 각 노드의 부모를 재귀적으로 따라 가는 형식을
경로 압축으로 고도화 하여 효율성을 높여 구현한다(find연산에서).

union연산의 경우 파라메터로 들어온 두 노드의 parent 값이 다른 경우
더 parent 값이 더 작은 쪽으로 합쳐지게끔 구현하거나
인자의 자리를 기준으로 설정하는 방법이 있으나 예시 코드는 전자이다.

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

class Main {
  static int[] parent;
  static int N,E; // 노드의 갯수(N)과 간선의 갯수(E)
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken()); 
    E = Integer.parseInt(st.nextToken());
    parent = new int[N+1];

    for(int i=0; i<N+1; i++){
      // 자기 자신으로 루트 노드 초기화
      parent[i] = i;
    }
    
    for (int i=0; i<E; i++){
      st = new StringTokenizer(br.readLine());
      int v1 = Integer.parseInt(st.nextToken());
      int v2 = Integer.parseInt(st.nextToken());
      union(v1,v2);
    }

    for (int i=1; i<N+1; i++) System.out.print(parent[i]+" ");
    System.out.println();
    for (int i=1; i<N+1; i++) System.out.print(findParent(i)+" ");
    System.out.println();
  }

  public static int findParent(int v){
    /*
    노드 갯수가 V, 간선의 갯수가 M이라 할때
    경롤 압축 기법을 적용하여 O(VM)-> O(V+MlogV)
    */
    if(v!= parent[v]) parent[v] = findParent(parent[v]);
    return parent[v];
  }
  public static boolean union(int v1, int v2){
    int pV1 = findParent(v1), pV2 = findParent(v2);

    // 만일 루트 노드가 다르다면 union해주고 true 반환
    if(pV1 != pV2){
      //더 작은 노드로 루트 노드를 갱신
      if(pV1<pV2) parent[v2] = pV1;
      else parent[v1] = pV2;
      return true;
    }
    //루트 노드가 같다면 false 반환
    else return false;
  }
  
}

서로소 집합으로 사이클 판별

만일 두 노드의 부모노드가 같은 경우 union 연산에서 false를 리턴하고 이미 부모노드 같은 상태에서 간선으로 연결 되어있기 떄문에 사이클이라고 판별 할 수 있다.

크루스칼 알고리즘

disjoint set을 이용하여 spanning tree(신장 트리)를 최소 비용으로 연결하는
MST를 구현한다.

아이디어

최소 비용으로 정렬하여 union연산이 가능한(부모 노드가 다른) 사이클이 형성 되지 않는 간선 만 연결하여 구현한다.