[SWEA] 3289. 서로소 집합(d4)

문제

---

초기에 {1}, {2}, ... {n} 이 각각 n개의 집합을 이루고 있다.

여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

연산을 수행하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 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 이하의 자연수이며 같을 수도 있다.

[출력]

각 테스트 케이스마다 1로 시작하는 입력에 대해서 같은 집합에 속해있다면 1을, 아니면 0을 순서대로 한줄에 연속하여 출력한다.

입력

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 001

풀이

---

문제 유형 : find-union 구현

코드

---

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

public class Solution_d4_3289_서로소집합 {
	
	static int n;
	static int[] parents;
	
	static void makeSet() {
		for(int i=0; i<=n; i++) {
			parents[i] = i;
		}
	}
	
	static int find(int a) {
		if(a==parents[a]) return a;
		return parents[a] = find(parents[a]);
	}
	
	static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		
		if(pa!=pb) parents[pb] = pa;
	}
    
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			answer.append("#").append(tc).append(" ");
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			parents = new int[n+1];
			makeSet();
			
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int com = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(com==0) {	// union 연산
					union(a, b);
				}else {	//같은 집합이면 1 아니면 0
					if( find(a)==find(b)) answer.append("1");
					else answer.append("0");
				}
			}
			
			answer.append("\n");
		}
		
		System.out.println(answer.toString());
		br.close();
	}

}

.java