dfs_bfs_2.cpp

/**
 * @file dfs_bfs.cpp
 * @author kim youngjin (youngjin.kim2@navercorp.com)
 * @brief depth-first-search, breathe-first-search
 * @date 2022-03-13
 * 
 * @copyright Copyright (c) 2022
 */
#include <bits/stdc++.h>

class Graph {

    int n;
    std::vector< std::vector<int> > adj;

    void erase_duplication() {
        for (int i = 1; i <= n; i++)
            erase_duplication(i);
    }

    void erase_duplication(int u) {
        std::vector<int> &arr = adj[u];
        erase_duplication(arr);
    }

    static void erase_duplication(std::vector<int> &arr) {
        std::sort(arr.begin(), arr.end());
        arr.erase(std::unique(arr.begin(), arr.end()), arr.end());
    }

    void reverse(int u) {
        std::reverse(adj[u].begin(), adj[u].end());
    }

public:

    Graph(int n, int m): n(n), adj(n+1) {
        int s, e;
        while (m--) {
            scanf("%d %d", &s, &e);
            adj[s].push_back(e);
            adj[e].push_back(s);
        }
        erase_duplication();
    }
    
    void reverse() {
        for (int i = 1; i <= n; i++)
            reverse(i);
    }

    const std::vector<int>& get_adj(int u) const {
        return adj[u];
    }

    int get_n() const { return n; }

};

class Scheduler {
public:

    virtual void push(int v) = 0;

    virtual int pop() = 0;

    virtual bool empty() const = 0;

    void clear() {
        while (!empty())
            pop();
    }

};

class DFSScheduler: public Scheduler {

    std::stack<int> s;

public:

    virtual void push(int v) { s.push(v); }

    virtual int pop() {
        int r = s.top();
        s.pop();
        return r;
    }

    virtual bool empty() const { return s.empty(); }

};

class BFSScheduler: public Scheduler {

    std::queue<int> q;

public:

    virtual void push(int v) { q.push(v); }

    virtual int pop() {
        int r = q.front();
        q.pop();
        return r;
    }

    virtual bool empty() const { return q.empty(); }

};

class UniqueChecker {

    std::vector<bool> tbl;

public:

    UniqueChecker(int sz): tbl(sz) {}

    bool set(int v) {
        bool r = tbl[v];
        tbl[v] = true;
        return r;
    }
    void clear() {
        std::fill(tbl.begin(), tbl.end(), false);
    }

};

class Traveler {

    const Graph &g;
    Scheduler &sched;
    UniqueChecker uc;

    void propagate(int u) {
        const auto a = g.get_adj(u);
        for (auto it = a.begin(); it != a.end(); it++) {
            sched.push(*it);
        }
    }
public:

    struct TravelResult {
        int node;
        bool term;
        TravelResult(int node = 0, bool term = false): node(node), term(term) {}
    };

public:

    Traveler(const Graph &g, Scheduler &sched): g(g), sched(sched), uc(g.get_n() + 1) {}

    void begin(int start) {
        uc.clear();
        sched.clear();
        sched.push(start);
    }

    TravelResult next() {
        while (!sched.empty()) {
            int u = sched.pop();
            if (uc.set(u))
                continue;
            propagate(u);
            return TravelResult(u, false);
        }
        return TravelResult(-1, true);
    }

};

void print_nodes(const Graph &g, Scheduler &&sched, int start) {
    Traveler::TravelResult u;
    Traveler t(g, sched);
    t.begin(start);
    while (!(u = t.next()).term) {
        printf("%d ", u.node);
    }
    puts("");
}

int main() {
    int n, m, start;
    scanf("%d %d %d", &n, &m, &start);

    Graph g(n, m);
    g.reverse();
    print_nodes(g, DFSScheduler(), start);
    g.reverse();
    print_nodes(g, BFSScheduler(), start);
    
    return 0;
}