BOJ : https://www.acmicpc.net/problem/1260
GitHub : https://github.com/junho0956/Algorithm/blob/master/1260/1260/%EC%86%8C%EC%8A%A4.cpp
dfs bfs 의 기본지식을 묻는 문제이다.
작은정점부터 방문하라 했으니 정렬을 해줘야한다.
더보기
|
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
|
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N, M, start;
int s, e;
vector<int> v[1001];
bool visit[1001];
void dfs(int start) {
if (visit[start]) return;
visit[start] = 1;
cout << start << " ";
for (int i = 0; i < v[start].size(); i++) {
dfs(v[start][i]);
}
}
void bfs(int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int cur = q.front();
q.pop();
if (visit[cur]) continue;
visit[cur] = 1;
cout << cur << " ";
for (int i = 0; i < v[cur].size(); i++) {
if (!visit[v[cur][i]]) q.push(v[cur][i]);
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> M >> start;
for (int i = 0; i < M; i++) {
cin >> s >> e;
v[s].push_back(e);
v[e].push_back(s);
}
for (int i = 1; i <= N; i++) sort(v[i].begin(), v[i].end());
dfs(start);
cout << '\n';
memset(visit, 0, sizeof(visit));
bfs(start);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 1707번 이분 그래프 (0) | 2020.01.13 |
|---|---|
| BOJ 11724번 연결 요소의 개수 (0) | 2020.01.13 |
| BOJ 2004번 조합 0의 개수 (0) | 2020.01.13 |
| BOJ 1676번 팩토리얼 0의 개수 (0) | 2020.01.13 |
| BOJ 10872번 팩토리얼 (0) | 2020.01.13 |