BOJ 1717 집합의 표현 java 자바

BOJ 1717 집합의 표현 java 자바

 

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

1717번: 집합의 표현

 

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

public class Main {
	static int n, m;
	static int[] parents;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		parents = new int[n+1];
		for (int i = 0; i <= n; i++) {
			parents[i] = i;
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int order = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			switch(order) {
			case 0:
				union(a, b);
				break;
			case 1:
				int p1 = find(a);
				int p2 = find(b);
				System.out.println(p1 == p2? "YES" : "NO");
				break;
			}
		}
		
	} // main
	
	static int find(int x) {
		if(parents[x] == x) return x;
		return parents[x] = find(parents[x]);
	}
	
	static void union(int x, int y) {
		int p1 = find(x);
		int p2 = find(y);
		
		parents[p2] = p1;
	}
}

 

 

크루스칼 알고리즘에서 쓰는 union and find 연산과 같다