백준 1717_집합의 표현(JAVA)

 

www.acmicpc.net/problem/1717

1717번: 집합의 표현

[문제 풀이]

유니온 파인드를 이용하여 문제를 풀었습니다.

 

이 집합의 원소들이 주어 졌을 때 0,1을 통해 원소의 집합을 합쳐주고 같은지 확인 하는 문제였습니다. 전형적인 유니온 파인드 문제임으로 이론은 아래 링크에 들어가시면 자세히 설명 되있습니다.

 

steady-life.tistory.com/128?category=788590

서로소 집합(Disjoint Set, Union-Find)

코드 설명

• n, m 을 입력 받고 배열 n을 초기화 시켜줍니다.
• m 만큼 반복하며 첫 번째 값이 0인 경우 union을 시켜줍니다.
• 첫 번째 값이 1인 경우 집합의 부모 값을 확인하여 같으면 "YES", 틀리면 "NO"를 출력합니다.

[코드]

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

class Main{
	
	static int[] parent;
	
	public static void union(int a, int b) {
		
		int parent_a = find(a);
		int parent_b = find(b);
		
		parent[parent_b] = parent_a;
	}
	
	public static int find(int a) {
		
		if(parent[a] == a)
			return a;
		else
			return parent[a] = find(parent[a]);
	}
	
	public static void main(String[] args) throws Exception{
	
		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());
		
		parent = new int[n+1];
		
		for(int i = 0; i <= n; i++)
			parent[i] = i;
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			
			int c = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(c == 0)
				union(a, b);
			else {
				if(find(a) == find(b))
					System.out.println("YES");
				else
					System.out.println("NO");
			}
		}		
	}
}