[백준 1717] 집합의 표현

 

처음 풀어보는 유니온파인드 문제이다.

 

후에 되새기는 용으로 간단히 서술해보겠다.

 

유니온파인드(Union-Find)는 자료구조의 이름으로 disjoint-set(서로소 집합)이라고도 부른다.

1개 혹은 그 이상의 집합들은 서로 교집합이 없고 그 집합들의 합집합은 전체집합과 같다.

이 자료구조는 Union 연산(합연산)과 Find 연산(루트 검색)만이 있다.

 

문제 풀이 및 유니온파인드 구현을 같이 했다.

 

public class Main {
    
    int tree[];
    int size;
    
    Main(int size) {
        tree = new int[size+1];
        this.size = size;
        
        Arrays.fill(tree, -1);
    }
    
    void set(int root, int child) {
        tree[child] = root;
    }
    
    int find(int n) {
        if(tree[n] < 0) return n;
        tree[n] = find(tree[n]);
        return tree[n];
    }
    
    void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b) return;
        tree[a] += tree[b];
        tree[b] = a;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        Main uf = new Main(n);
        while(m-->0) {
            st = new StringTokenizer(br.readLine());
            int status = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(status == 0)
                uf.union(a, b);
            else
                System.out.println(uf.find(a) == uf.find(b) ? "YES" : "NO");
        }
    }
}