-
Notifications
You must be signed in to change notification settings - Fork 0
/
P053_SWEA7465_창용마을무리의개수.java
65 lines (46 loc) · 1.37 KB
/
P053_SWEA7465_창용마을무리의개수.java
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.io.BufferedReader;
import java.io.InputStreamReader;
// 서로소 집합
public class P053_SWEA7465_창용마을무리의개수 {
static int N;
static int M;
static int[] parent;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
String[] s = br.readLine().split(" ");
N = Integer.parseInt(s[0]);
M = Integer.parseInt(s[1]);
make(); // 서로소 집합 생성
for (int m = 0; m < M; m++) {
s = br.readLine().split(" ");
int A = Integer.parseInt(s[0]);
int B = Integer.parseInt(s[1]);
union(A, B); // 집합 합치기
}
int answer = 0;
for (int i = 1; i <= N; i++) {
if (find(i) == i) // 부모가 본인일 경우
answer++;
}
System.out.println("#" + t + " " + answer);
}
}
static int find(int a) { // a의 대표자 찾기
if (parent[a] == a) return a;
return parent[a] = find(parent[a]); // 우리의 대표자를 나의 부모로.. : path compression
}
static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot == bRoot) return;
parent[bRoot] = aRoot;
}
static void make() {
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
}