집합의 표현 ( 백준 1717번 )

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

 

* UnionFind 알고리즘 문제

* 연산이 주어지는데

- 0이면 a가 포함되어있는 집합과 b가 포함되어 있는 집합을 합친다는 의미

- 1이면 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산

* 1연산을 진행했을때 포함되었으면 YES, 아니면 NO를 출력하면 된다.

 

UnionFind 알고리즘 사용하기만 하면 풀리는 문제라서 개념은 따로 정리하겠다.

아래는 코드.

 

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

public class BOJ1717 {
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        parents = new int[N+1];
        for(int i = 0; i <= N; i++) {
            parents[i] = i;
        }
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());
            //union
            if(op == 0) {
                union(nodeA, nodeB);
            }
            //isConnected
            else {
                if(isConnected(nodeA, nodeB)) {
                    sb.append("YES").append("\n");
                }
                else {
                    sb.append("NO").append("\n");
                }
            }
        }
        System.out.println(sb);
    }
    private static int find(int node) {
        if(node != parents[node]) {
            node = find(parents[node]);
        }
        return parents[node];
    }
    private static void union(int nodeA, int nodeB) {
        int rootA = find(nodeA);
        int rootB = find(nodeB);

        if(rootA != rootB) {
            parents[rootB] = rootA;
        }
    }
    private static boolean isConnected(int nodeA, int nodeB) {
        return find(nodeA) == find(nodeB);
    }
}

 

* WQU ( Weighted Quick Union ) 까지는 사용하지 않고 Path Compression 사용하여 구현.