문제
초기에 {0}, {1}, ..., {n}으로 n+1개의 집합이 있다. 합집합 연산과 두 원소가 같은 집합에 속하는지 확인하는 연산을 처리하는 문제이다.
입력
첫째 줄에 n (1 ≤ n ≤ 1,000,000)과 m (1 ≤ m ≤ 100,000)이 주어진다. 다음 m개의 줄에 연산이 주어진다:
0 a b: a와 b가 속한 집합을 합친다.1 a b: a와 b가 같은 집합에 속하는지 확인한다.
출력
1 연산마다 같은 집합이면 YES, 아니면 NO를 출력한다.
예제
입력
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 0 4
0 5 2
1 0 5출력
NO
NO
YES풀이
핵심 아이디어: Union-Find(분리 집합) 자료구조를 구현한다. 경로 압축(Path Compression)을 통해 find 연산을 거의 O(1)에 수행할 수 있다.
- 초기화:
p[i] = i(각 원소는 자기 자신이 루트) find(a): a의 루트를 찾으면서 경로 압축 적용 →p[a] = a == p[a] ? a : find(p[a])union(a, b):find(a)와find(b)가 다르면 하나를 다른 것의 루트로 설정1연산 시:find(a) == find(b)이면YES, 아니면NO
경로 압축을 적용하면 연속 find 호출의 상각 시간 복잡도가 역 아커만 함수 α(N)으로 매우 작아진다.
코드
package day399;
import java.io.*;
import java.util.*;
class Main {
static int N, M;
static int[] p;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
p = new int[N + 1];
for (int i = 1; i < N + 1; i++)
p[i] = i;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int cmd = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (cmd == 0)
union(a, b);
else if (cmd == 1)
sb.append(find(a) == find(b) ? "YES\n" : "NO\n");
}
System.out.println(sb);
br.close();
}
private static boolean union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) // 사용안함
return false;
p[b] = a;
return true;
}
private static int find(int a) {
return p[a] = a == p[a] ? a : find(p[a]);
}
}복잡도
- 시간: O(M α(N)) — M개의 연산, 경로 압축으로 find가 상각 O(α(N))
- 공간: O(N) — 부모 배열 p