[SW Academy] 3289 서로소 집합 - JAVA

1. 문제 유형 : union-find

2. 시간복잡도 : O(NM)

 

유니온파인드를 적용할 수 있는 간단한 예시 문제였다.

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

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");
			st = new StringTokenizer(in.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int[] parents = new int[N+1];	// 각 원소의 대표자 인덱스 저장
			makeSet(parents);	// 초기에는 자신이 대표자

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(in.readLine());
				int cmd = Integer.parseInt(st.nextToken());
				if(cmd == 0) {
					// UNION
					union(parents, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
				}else {
					// CHECK
					sb.append(checkSet(parents, Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	public static void makeSet(int[] parents) {
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}
	}
	
	public static int findSet(int[] parents, int a) {
		if(a == parents[a]) return a;
		return parents[a] = findSet(parents, parents[a]);	// path compression
	}

	public static void union(int[] parents, int a, int b) {
		int aRoot = findSet(parents, a);
		int bRoot = findSet(parents, b);
		if(aRoot == bRoot) return;
		
		parents[bRoot] = aRoot;
	}
	
	public static int checkSet(int[] parents, int a, int b) {
		int aRoot = findSet(parents, a);
		int bRoot = findSet(parents, b);
		if(aRoot == bRoot) return 1;
		return 0;
	}
}