[Algorithm] union-find

union-find

주의

find 연산 시, 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견하면 대표 노드로 변경하는 부분.

union 연산에서 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분.

사진 출처 : https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/

 

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

import java.io.*;
import java.util.*;

public class Main {
    static int[] num;
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n=input[0], m=input[1];

            num = new int[n+1];
            for(int i=0; i<=n; i++){
                num[i]=i;
            }

            for(int i=0; i<m; i++){
                int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                if(data[0]==0) union(data[1], data[2]);
                else System.out.println(find(data[1]) == find(data[2]) ? "YES" : "NO");
            }
        } catch(Exception e){
            System.out.println(e);
        }
    }

    static void union(int a, int b){
        int aa = find(a);
        int bb = find(b);
        if(aa != bb) num[bb]=aa;
    }

    static int find(int n){
        if(num[n] == n){
            return n;
        } else {
            return num[n] = find(num[n]);
        }
    }
}