문제/백준
백준 11724번 연결 요소의 개수_Union Find [JAVA]
javaju
2021. 11. 17. 01:12
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주
www.acmicpc.net
풀이 과정
방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제였습니다.
저는 Union Find 알고리즘을 이용하여 문제를 풀었으며,
각각의 간선의 부모(Find)가 다른 경우 Union 메서드를 통해 간선을 연결시켜 주었습니다.
M번의 반복문이 끝난 뒤, HashSet을 이용해 연결요소의 개수를 구해주었습니다.
[같은 문제의 배열 풀이방법]
백준 11724번 연결 요소의 개수 [JAVA]
문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N
javaju.tistory.com
코드
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main_BJ_11724_연결요소의개수 {
static int N,M;
static int [] parents;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashSet<Integer> hs = new HashSet<>();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parents = new int[N+1];
for(int i=1;i<parents.length;i++) parents[i] = i;
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(find(u)!=find(v)) union(u,v);
}
for(int i=1;i<parents.length;i++) {
hs.add(find(parents[i]));
}
System.out.println(hs.size());
}
public static void union(int a,int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot>bRoot) parents[aRoot] = bRoot;
else parents[bRoot] = aRoot;
}
public static int find(int a) {
if(parents[a]==a) return a;
return parents[a] = find(parents[a]);
}
}
|
cs |