<Algorithm> 48. 1717번 집합의 표현

1. 1717번 집합의 표현

• 기본 UnionFind 문제 , UnionFind는 어떤 노드가 있을 때 루트의 크기를 비교해서 하나의 집합으로 만들어 주는 알고리즘이다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        ArrayList<String> ans =new ArrayList<>();
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Node[] node = new Node[N + 1];
        
        for(int i = 0 ; i < N + 1; i++) {
            node[i] = new Node(i,0);
        }// 최초의 부모는 자기자신
        Union u = new Union(node);
        
        for(int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            int z = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if(z == 0) {
                u.uni(a,b);
            }else {
                if(u.check(a, b)) {
                    ans.add("yes");
                }else {                    
                    ans.add("no");
                }
            }
        }
        
        for(String str : ans) {
            System.out.println(str);
        }
        
    }
                
}
class Union{
    
    Node[] node;
    public Union(Node[] node) {
        this.node = node;
    }
    
    public int find(int i) {
        if(node[i].parent != i) {
            return find(node[i].parent); // return 하지않으면 런타임 오류 발생
        }
        return node[i].parent;
    }
    
    public void uni(int i, int j) {
        int iroot = find(i);
        int jroot = find(j);
        
        if(iroot == jroot) return;
        // 같은 집합에 있다
        
        if(node[iroot].rank > node[jroot].rank) {
            node[jroot].parent = iroot;
        // j를 i에 병합
        }else if(node[iroot].rank < node[jroot].rank) {
            node[iroot].parent = jroot;
        
        }else {
            node[jroot].parent = iroot;
            node[iroot].rank += 1;
        } // 같을 경우 아무거나 붙여주고 rank( 노드의 깊이를 하나 추가 한다 )
        
    }
    public boolean check(int i, int j) {
        int iroot = find(i);
        int jroot = find(j);
        if(iroot == jroot) return true;
        return false;
    } // 같은 집합에 있는지 확인
}
class Node{
    int parent,rank;
 
    public Node(int parent, int rank) {
        super();
        this.parent = parent;
        this.rank = rank;
    }
}