boj)11724 - 연결 요소의 개수
2020. 11. 2. 18:29ㆍPS/boj
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.*;
import java.util.*;
public class boj_11724 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Queue<Integer> q = new LinkedList<>();
static boolean[] v;
static ArrayList<Integer>[] list;
static int N, M, x, y, ans;
public static void main(String[] args) throws IOException {
input();
solve();
System.out.println(ans);
}
static void input() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
v = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
list[i] = new ArrayList<Integer>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
list[x].add(y);
list[y].add(x);
}
}
static void solve() {
for (int i = 1; i <= N; i++) {
if (!v[i]) {
bfs(i);
ans++;
}
}
}
static void bfs(int node) {
q.offer(node);
while (!q.isEmpty()) {
int now = q.poll();
for (int i = 0; i < list[now].size(); i++) {
int next = list[now].get(i);
if (!v[next]) {
v[next] = true;
q.offer(next);
}
}
}
}
}
|
cs |
- 1차 실패
- 인접리스트로 구현하려니까 실패함
- 가급적 인접 행렬보단 인접 리스트를 사용 -> 더 효율적
- 방문하지 않은 정점에서 bfs 시작 -> 연결 요소 ++
'PS > boj' 카테고리의 다른 글
boj)4963 - 섬의 개수 (0) | 2020.11.03 |
---|---|
boj)1707 - 이분그래프 (0) | 2020.11.03 |
boj)5014 - 스타트링크 (0) | 2020.11.02 |
boj)2146 - 다리 만들기 (0) | 2020.11.02 |
boj)13023 - ABCDE (0) | 2020.10.29 |