백준 1717[자바] java 집합의 표현

문제 링크: https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

▶문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

---

▶입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

---

▶출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

---

▶해설

최소 스패닝 트리 문제입니다. 각 원소의 부모를 비교하여 다를 경우 union하면 같은 집하에 속한 것으로 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
    static int n, m;
    static int [] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        StringBuilder sb = new StringBuilder();
        parents = new int [n+1];
        for(int i=0; i<=n; i++){
            parents[i]=i;
        }
        int op, e1, e2;
        int result=-1;
        for(int i=0; i<m; i++){
            String[] s = br.readLine().split(" ");
            op=Integer.parseInt(s[0]);
            e1=Integer.parseInt(s[1]);
            e2=Integer.parseInt(s[2]);
            if(op==0){
                if(!isParent(e1, e2)){
                    union(e1,e2);
                }
            }
            else{
                if(!isParent(e1,e2)){
                    sb.append("NO").append("\n");
                }
                else{
                    sb.append("YES").append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
    private static boolean isParent(int a, int b){
        a = find(a);
        b= find(b);
        if(a==b){
            return true;
        }
        else{
            return false;
        }
    }
    private static int find(int a){
        if(parents[a]==a){
            return a;
        }
        else{
            return parents[a] = find(parents[a]);
        }
    }
    private static void union(int a, int b){
        a=find(a);
        b= find(b);
        parents[b]=a;
    }
}