BOJ-1260

#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
 
using namespace std;

class Graph {
    int V;
    list<int> *adj;
    public:
        Graph(int V);
        void addEdge(int v, int w);
        void DFS(int s);
        void BFS(int s);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V+1];
}

void Graph::addEdge(int v, int w) {
    // adj[v].push_back(w);
    adj[v].push_front(w);
    adj[w].push_front(v);
    adj[v].sort(std::greater<int>()); // descending sort
    adj[w].sort(std::greater<int>());
}

void Graph::DFS(int s) {
    vector<bool> visited(V+1, false);
    stack<int> stack;
    stack.push(s);

    while (!stack.empty()) {
        int top = stack.top(); // TOP == S
        stack.pop();

        if (!visited[top]) {
            cout << top << " ";
            visited[top] = true;
        }

        for (auto i = adj[top].begin(); i != adj[top].end(); ++i) {
            if (!visited[*i])
                stack.push(*i);
        }
    }
}

void Graph::BFS(int s) {
    vector<bool> visited(V+1, false);
    queue<int> queue;
    visited[s] = true;
    queue.push(s);

    while (!queue.empty()) {
        int front = queue.front(); // FRONT == S
        cout << front << " ";
        queue.pop();

        for (auto i = adj[front].end(); i-- != adj[front].begin();) { // reverse iterator
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push(*i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, M, V; // N : 정점, Vertex M: 간선, Edge
    cin >> N >> M >> V;

    Graph graph(N);
    int a, b;
    for (int i=0; i<M; i++) {
        cin >> a >> b;
        graph.addEdge(a, b);
    }
    
    graph.DFS(V);
    cout << "\n";
    graph.BFS(V);
}