dfs와 bfs를 할 줄 아는가 묻는 문제이다. 정점과의 연결을 벡터로 저장해주고 dfs와 bfs를 돌려주었다. 현재 정점과 연결된 정점이 여러 개인 경우 번호가 작은 정점부터 방문하도록 오름차순으로 정렬을 해주었다. dfs와 bfs를 돌면서 도착한 정점을 차례대로 출력해주었다.
간단한 문제였다. 처음 정렬을 해주는 부분에서 범위 설정을 잘못해주어 시간을 낭비했다. 주의하자.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int N, M, V;
vector<int> v[1001];
vector<int> tmp[1001];
bool visit[1001];
void dfs(int n) {
for (int i = 0; i < v[n].size(); i++) {
if (visit[v[n][i]]) continue;
cout << v[n][i] << " ";
visit[v[n][i]] = true;
dfs(v[n][i]);
}
}
void bfs() {
queue<int> q;
q.push(V);
visit[V] = true;
cout << V << " ";
while (!q.empty()) {
int n = q.front();
q.pop();
for (int i = 0; i < v[n].size(); i++) {
if (visit[v[n][i]]) continue;
q.push(v[n][i]);
visit[v[n][i]] = true;
cout << v[n][i] << " ";
}
}
}
void solution() {
for (int i = 1; i <= N; i++) {
sort(v[i].begin(), v[i].end());
}
cout << V << " ";
visit[V] = true;
dfs(V);
cout << "\n";
memset(visit, 0, sizeof(visit));
bfs();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M >> V;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
solution();
return 0;
}