BOJ - 1717 ) 집합의 표현

 

---

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

1717번: 집합의 표현

---

합집합의 연산을 반복하면서, 특정 두 원소가 같은 집합에 속해있는지를 묻는 문제이다.

 

이 문제는 "너 서로소집합 메소드 구현할줄알아?"라고 물어보는 문제이다.

 

Rank를 계산하여 Union연산을 하는 것(Rank Compression)은 일반 코테에 자주 나오지는 않지만, 

 

MST를 구성할 때 사용되는 크루스칼,프림알고리즘은 정형화 되어있어서 빠르게 습득하면 관련문제를

 

쉽게 풀수있다. 또한, Union연산시에, 경로 압축 ( Path Compression )을 통하여 합집합 연산을 해준다.

 

---

import java.util.Scanner;

public class Main {
	static int parent[];
	public static int find(int a) {
		if(parent[a] == a) return a;
		return find(parent[a]);
	}
	public static void union(int a , int b) {
		// 부모끼리 합친다.
		int pa = find(a);
		int pb = find(b);
		if(pa==pb) return;
		if(pa>pb) { parent[pb] = pa;}
		else { parent[pa] = pb;}
	}
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		parent = new int[n+1];
		for(int i = 0 ; i <= n ; i ++) parent[i] =i;
		for(int i = 0 ; i < m ; i ++) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(a == 0) {
			union(b,c);
		}else {
			if(find(b) == find(c)) {
				System.out.print("YES\n");
			}else {
				System.out.print("NO\n");
			}
		}
	}
	}
}

---