dfs_bfs.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());
    }

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();
    }

    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() = 0;

};

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() { 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() { 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;

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

    void propagate_reverse(int u) {
        const auto a = g.get_adj(u);
        for (auto it = a.rbegin(); it != a.rend(); it++) {
            sched.push(*it);
        }
    }

public:

    Traveler(const Graph &g, Scheduler &sched): g(g), sched(sched) {}

    void travel(int start, std::function<void(int)> on_visit, bool reverse = false) {
        UniqueChecker uc(g.get_n() + 1);

        sched.push(start);
        
        while (!sched.empty()) {
            int u = sched.pop();
            if (uc.set(u))
                continue;
            on_visit(u);
            if (reverse)
                propagate_reverse(u);
            else
                propagate(u);
        }
    }

};

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

    Graph g(n, m);

    std::function<void(int)> on_visit = [](int v) {
        printf("%d ", v);
    };

    DFSScheduler dfs_sched;
    Traveler dfs_traveler(g, dfs_sched);
    dfs_traveler.travel(v, on_visit, true);
    puts("");

    BFSScheduler bfs_sched;
    Traveler bfs_traveler(g, bfs_sched);
    bfs_traveler.travel(v, on_visit);
    puts("");

    return 0;
}

Refer here

Another version here