ALGORITHM/BOJ
[백준] 1717 집합의 표현
0298
2021. 8. 14. 19:42
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
2021-08-14
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import java.io.*;
import java.util.*;
public class Main1717 {
public static int[] parent;
public static int n, m;
public static int find(int x) {
if(x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
public static void union(int x, int y) { // y > x
x = find(x);
y = find(y);
if(x != y) parent[y] = x;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i = 1; i <= n; i++) parent[i] = i; // init
for(int i = 0;i < m; i++) {
st = new StringTokenizer(bf.readLine());
int op = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(op == 0) { //union
if(a > b) {
int tmp = b;
b = a;
a = tmp;
}
union(a, b);
} else { // find
if(find(a) == find(b)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
|
cs |
#문제풀이
Union-find
