[백준] 자바 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 를 출력해도 된다)

---

테스트 케이스

 

입력 1

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

출력 1

NO

NO

YES

---

접근

대놓고 UNION-FIND 문제 입니다.

UNION-FIND를 구현하면 그냥 문제가 해결 됩니다.

 

UNION-FIND란 ->

UNION : 합치기

FIND : 찾기

각각 다른 서로소 집합들을 합치거나, 최상위 부모를 찾거나 하는 연산을 의미합니다.

---

코드

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

public class Main {
	static int n,m,parent[];
	
	static public void makeSet() {
		parent = new int[n+1];
		for(int i=0; i<=n; i++) {
			parent[i] = i;
		}
	}
	static public int findParent(int a) {
		if(parent[a] == a) return a;
		return parent[a] = findParent(parent[a]);
	}
	static public boolean union(int a, int b) {
		int aRoot = findParent(a);
		int bRoot = findParent(b);
		if(aRoot == bRoot) return false;
		parent[bRoot] = aRoot;
		return true;
	}
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    n = Integer.parseInt(st.nextToken());    
	    m = Integer.parseInt(st.nextToken());
	    StringBuilder sb = new StringBuilder();
	    makeSet();
	    for(int i=0; i<m; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	int instruction = Integer.parseInt(st.nextToken());
	    	int num1 = Integer.parseInt(st.nextToken());
	    	int num2 = Integer.parseInt(st.nextToken());
	    	if(instruction == 0) {
	    		union(num1,num2);
	    	}
	    	else {
	    		if(findParent(num1) == findParent(num2)) sb.append("YES"+"\n");
	    		else sb.append("NO"+"\n");
	    	}
	    }
	    bw.write(sb.toString());
	    br.close();
	    bw.flush();
	    bw.close();
	    }
	}

---

주의

X