백준
백준 소스코드 [C++] 1260 DFS와 BFS
Hani_Levenshtein
2020. 11. 13. 12:42
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
백준 소스코드 [C++] 1260 DFS와 BFS
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
int n, m, v;
int graph[1001][1001];
bool dfsvisit[1001], bfsvisit[1001];
void input() {
cin >> n >> m >> v;
int S, E;
for (int i = 0;i < m;i++) {
cin >> S >> E;
graph[S][E]++;
graph[E][S]++;
}
}
void dfs(int a) {
cout << a << " ";
dfsvisit[a] = true;
for (int i = 1;i <= n;i++) {
if (graph[a][i] != 0 && dfsvisit[i] == false) {
dfsvisit[i] = true;
dfs(i);
}
}
return;
}
void bfs() {
queue <int> q;
q.push(v);
bfsvisit[v] = true;
while (q.empty() != true) {
int t = q.front();
q.pop();
for (int i = 1;i <= n;i++) {
if (graph[t][i] != 0 && bfsvisit[i] == false) {
q.push(i);
bfsvisit[i] = true;
}
}
cout << t << " ";
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
dfs(v);
cout << '\n';
bfs();
return 0;
}