[BOJ]1717번 : 집합의 표현

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

1717번: 집합의 표현

 

분류 : Disjoint-Set

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

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {

    static PrintWriter out;
    //root[a] = b -> a의 부모는 b이다.
    static int[] root = new int[2000001];
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int T = sc.nextInt();
        int F = sc.nextInt();
        // root 초기화
        for (int i = 1; i <= T; i++)
        {
            root[i] = i;
        }
        for (int i = 0; i < F; i++)
        {
                int O = sc.nextInt();
                if (O == 0)
                {
                    int a = sc.nextInt();
                    int b = sc.nextInt();
                    Union(a, b); //a와 b를 Union
                }
                else if (O == 1)
                {
                    int a = sc.nextInt();
                    int b = sc.nextInt();
                    a = Find(a);
                    b = Find(b);
                    out.println(a == b ? "YES" : "NO");
                }
            }
        out.flush();
    }
    private static void Union(int a, int b) {
        a = Find(a);
        b = Find(b);
        if (a != b) {
            root[a] = b;
        }
    }
    private static int Find(int k) {
        if (k == root[k])
            return k;
        return root[k] = Find(root[k]);

    }
}

 

Disjoint-Set, Union-Find 기초 문제

0 일시에 a, b를 Union 하고

1 일시에 Find를 통해 a, b의 루트를 찾고 서로 비교한다.