[코테 매일 풀기 3일차] 1027

백준 1717 집합의 표현

아이디어

• union -find 알고리즘 사용하기
• 경로 압축 -> nodes[n] = find(nodes[n])
• union: 두개의 노드의 부모노드를 union시켜야함 (nodes[find(a)] = find(b))

package boj_gold.p1717_집합의표현;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Review2 {
    static int [] nodes;
    public static void main(String[] args) throws IOException {
        //union -find 사용
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()) ;

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken()); //연산의 개수
        // 1-7까지 담기
        nodes = new int [N+1];
        for (int i = 1; i<=N; i++){
            nodes[i] = i;
        }
        //0 은 합집합 , 1은 같은 집합인지 확인
        for (int i = 0; i < M; i++){
            st = new StringTokenizer(bf.readLine()) ;
            int cmd = Integer.parseInt(st.nextToken());
            int a =  Integer.parseInt(st.nextToken());
            int b =  Integer.parseInt(st.nextToken());
            if(cmd ==0) {
                union(a, b);
            }else if (cmd ==1){
                if (find(a) == find(b)){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }//
            }
        }//for
    }
    static void union(int a, int b ){
        //만약 같은 집합이면
        if (find(a) == find(b)) { //같은 부모이면
            return;
        }
        int rootA = find(a);
        int rootB = find(b);

        nodes[rootB] = rootA;
    }//

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

}