dfs_bfs.cpp

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define MAX_VALUE 1001 // (1<= N <= 1000)
int jeongjum;
int gansun;
int start_jeongjum;
int mat[MAX_VALUE][MAX_VALUE];
int visit[MAX_VALUE];

// 4 5 1
// 1 2
// 1 3
// 1 4
// 2 4
// 3 4


void dfs(int v) {
    
    cout << v << ' ' ;
    visit[v] = 1;            //방문한 노드를 visit 0에서 1로 변경
    for(int i=1; i<=jeongjum; i++) {
        if(visit[i] == 1 || mat[v][i] == 0)     
            continue;
        dfs(i);                //dfs에서 재귀를 사용
    }
}

void bfs(int v) {
    queue<int> q;            //bfs에서는 q를사용
    q.push(v);
    visit[v] = 0;            //방문한 노드를 visit 1에서 0으로 변경
    while(!q.empty()) {
        v = q.front();
        cout << q.front() << ' ';
        q.pop();
        for(int i=1; i<=jeongjum; i++) {
            if(visit[i] == 0 || mat[v][i] == 0)
                continue;
            q.push(i);
            visit[i] = 0;
        }
    }
}



int main (){
    

    std::cin >> jeongjum;
    std::cin >> gansun;
    std::cin >> start_jeongjum;

    int x, y;  // for 간선
    for(int i=0; i<gansun; i++) {
        cin >> x >> y;            
        mat[x][y] = mat[y][x] = 1; // 양방향
    }

    dfs(start_jeongjum);            
    cout << '\n';
    bfs(start_jeongjum);
    return 0;
}