[KOITP] 동맹의 동맹은 동맹

출    처 : http://koitp.org/problem/SDS_PRO_3_2/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	2639	491 (19%)	382

문제

낙성마을에는 N명의 사람이 있다. 편의상 각 사람들을 1번부터 N번까지 번호를 매기도록 하자. 처음 이 사람들은 서로를 모르기 때문에, '적대 관계'를 갖고 있다.

하지만 언제까지나 '적대 관계'로 살아갈 수는 없는 법이다. 이 마을의 사람들은 한 두명씩 '동맹 관계'를 맺기로 하였다. 당연히 어떤 사람 A와 B가 동맹 관계를 맺으면, 자연스럽게 A의 동맹들과 B의 동맹들도 서로 동맹 관계를 맺게 된다. 이런 관계들이 많아지다보니 점점 더 복잡한 구조의 동맹 관계가 구성되게 되었다. 누가 누구와 동맹 관계인지 확실히 알기 위해, 이런 관계를 찾아내는 프로그램을 작성하기로 하였다.

동맹 관계를 쉽게 알아내는 프로그램을 작성하시오.

입력

첫 번째 줄에 낙성마을의 사람의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에 질의의 수 Q가 주어진다. (1 ≤ Q ≤ 200,000)

세 번째 줄부터 Q개의 줄에 걸쳐 질의가 주어진다. 각 질의는 다음의 형태 중 하나로 주어진다. (1 ≤ a, b ≤ N)

• 0 a b : a번 사람과 b번 사람이 동맹 관계를 맺었음을 의미하는 질의이다.
• 1 a b : a번 사람과 b번 사람이 동맹 관계에 있는지 물어보는 질의이다.

출력

1로 시작하는 모든 질의에 대해, 각 줄에 하나씩 동맹 관계가 아니면 0, 동맹 관계이면 1을 출력한다.

힌트

입력 예제

7 
9
0 1 3
1 1 7
0 7 6
1 3 7
0 3 7
0 4 2
0 1 3
1 1 7
1 1 1

출력 예제

0
0
1
1

< Comment >

 자료구조를 설명을 듣고 풀었기 때문에 비교적 난이도에 비해 수월하게 풀 수 있었습니다. Union and Find 라는 이름에 맞게  집합을 나누고 이를 그룹별로 파악하는 과정에 적합한 자료구조였습니다. 다만 처음에 시간제한 초과가 난 것은 리턴하는 과정에서 나중에 Find를 수행하더라도 최대한 짧게 수행되도록 find 하고 recursive 하게 되 돌아올때, 각각 원소들의 부모 원소를 최상단 노드로 갱신해주면서 돌아오도록 코딩을 해 주어야 했습니다. 해당 과정이 없을 경우에 호출수가 많이 늘어나 결과적으로 많이 느려짐을 확인했습니다.

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

public class FriendsFriend {
	
	public static int N = 0;
	public static int Q = 0;
	
	public static int unionFind[] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		Q = Integer.parseInt(br.readLine());
		
		unionFind = new int[N+1];
		for (int i = 1 ; i <= N ; i++) {
			unionFind[i] = i;
		}
		
		StringTokenizer st = null;
		
		int isQ = 0;
		int num1 = 0;
		int num2 = 0;
		
		int root1 = 0;
		int root2 = 0;
		
		for (int q = 0 ; q < Q ; q++) {
			
			st = new StringTokenizer(br.readLine());
			
			isQ = Integer.parseInt(st.nextToken());
			
			num1 = Integer.parseInt(st.nextToken());
			num2 = Integer.parseInt(st.nextToken());
			
			root1 = findRoot(num1);
			root2 = findRoot(num2);
			
			if (isQ == 0) {			// UNION
				unionFind[root2] = root1; 
			} else {				// Question
				
				if (root1 == root2) {
					bw.write("1\n");
				} else {
					bw.write("0\n");
				}
			}
		}
		bw.flush();
		bw.close();
	}
	
	public static int findRoot(int a) {
		
		if (unionFind[a] == a) {
			return a;
		}

		return unionFind[a] = findRoot(unionFind[a]);
	}
}