boj 1717 집합의 표현

www.acmicpc.net/problem/1717

1717번: 집합의 표현

union-find를 사용해볼 수 있는 문제입니다.

 

합집합 연산은 0 a b 형태로 주어지고, a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합친다는 의미입니다.

두 집합이 같은 집합인지 확인하는 연산은 1 a b 형태로 주어지고, a와 b가 같은 집합이면 YES, 아니면 NO를 출력하는 문제입니다.

 

저는 일단 parent배열에 집합의 루트를 자신으로 저장해놓고, union_find를 통해 a의 루트와 b의 루트를 찾아서

합치거나, 같은 집합인지 확인하였습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int parent[] = new int[1000001];
    static int N, M;
 
    static int find(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = find(parent[v]);
    }
 
    static void union(int u, int v) {
        int a = find(u);
        int b = find(v);
 
        if (parent[a] != parent[b])
            parent[b] = parent[a];
    }
 
    static void func() throws Exception {
        StringBuffer sb = new StringBuffer();
        int type, u, v;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            type = Integer.parseInt(st.nextToken());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            if (type == 0)
                union(Math.min(u, v), Math.max(u, v));
            else {
                if (find(u) == find(v))
                    sb.append("YES\n");
                else
                    sb.append("NO\n");
            }
        }
        
        System.out.print(sb.toString());
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        func();
    }
}