AlgoLib/DepthFirstOrder.h at master · 4eetah/AlgoLib · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#pragma once
#include <vector>
#include "Digraph.h"

class DepthFirstOrder
{
    using Bag = std::vector<int>;
    std::vector<bool> marked;
    std::vector<int>  m_pre;
    std::vector<int>  m_post;
    Bag m_preorder;
    Bag m_postorder;
    int preCounter;
    int postCounter;
public:

    DepthFirstOrder(Digraph& G)
    : marked(G.V(), false), m_pre(G.V()), m_post(G.V()),
      preCounter(0), postCounter(0)
    {
        for (int v = 0; v < G.V(); ++v)
            if (!marked[v]) dfs(G, v);
    }

    void dfs(Digraph& G, int v) {
        marked[v] = true;
        m_pre[v] = preCounter++;
        m_preorder.push_back(v);
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
        m_post[v] = postCounter++;
        m_postorder.push_back(v);
    }

    int pre(int v) const {
        return m_pre[v];
    }

    int post(int v) const {
        return m_post[v];
    }

    Bag preorder() const {
        return m_preorder;
    }

    Bag postorder() const {
        return m_postorder;
    }

    // This is actually a topological sort order
    Bag reversePost() const {
        return Bag(m_postorder.rbegin(), m_postorder.rend());
    }
};