https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
분류 : Disjoint-Set
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
static PrintWriter out;
//root[a] = b -> a의 부모는 b이다.
static int[] root = new int[2000001];
public static void main(String[] args) throws IOException {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int T = sc.nextInt();
int F = sc.nextInt();
// root 초기화
for (int i = 1; i <= T; i++)
{
root[i] = i;
}
for (int i = 0; i < F; i++)
{
int O = sc.nextInt();
if (O == 0)
{
int a = sc.nextInt();
int b = sc.nextInt();
Union(a, b); //a와 b를 Union
}
else if (O == 1)
{
int a = sc.nextInt();
int b = sc.nextInt();
a = Find(a);
b = Find(b);
out.println(a == b ? "YES" : "NO");
}
}
out.flush();
}
private static void Union(int a, int b) {
a = Find(a);
b = Find(b);
if (a != b) {
root[a] = b;
}
}
private static int Find(int k) {
if (k == root[k])
return k;
return root[k] = Find(root[k]);
}
}
Disjoint-Set, Union-Find 기초 문제
0 일시에 a, b를 Union 하고
1 일시에 Find를 통해 a, b의 루트를 찾고 서로 비교한다.
'PS' 카테고리의 다른 글
[BOJ]10974번 : 모든 순열 (0) | 2017.03.29 |
---|---|
[BOJ]11657번 : 타임 머신 (0) | 2017.03.28 |
[BOJ]4195번 : 친구 네트워크 (0) | 2017.03.25 |
[BOJ]1976번 : 여행 가자 (0) | 2017.03.25 |
[BOJ]1788번 : 피보나치 수의 확장 (0) | 2017.03.24 |