critical vertices

main.cc

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

template <typename T, typename V>
T& operator<<(T& t, V v)
{
    t.push_back(v);
    return t;
}

template <typename T, typename V>
bool Has(const T& t, const V& v)
{
    return std::find(t.begin(), t.end(), v) != t.end();
}

struct graph_t {
    int Size() const
    {
        return _nv;
    }

    void SetSize(int n)
    {
        _nv = n;
        --n;
        _d.reserve(n * n);
    }

    void Resize(int n)
    {
        _nv = n;
        --n;
        _d.resize(n * n);
    }

    bool Connected(int row, int col) const
    {
        if (row >= _nv-1 || col >= _nv-1)
            return false;

        int off = row * (_nv-1) + col;
        return _d[off];
    }

    graph_t& operator<<(int e)
    {
        _d.push_back(e != 0 ? true : false);
        return *this;
    }

private:
    std::vector<bool> _d;
    int _nv;
};

typedef std::deque<int> path_t;

struct level_t
{
    int v;
    path_t sub;
};

std::vector<path_t> Search(const graph_t& g)
{
    std::vector<path_t> paths;

    std::deque<level_t> levels;
    path_t visited;

    level_t next;
    next.v = 0;
    levels.push_back(next);

    while (!levels.empty()) {
        level_t& l = levels.back();
        visited.push_back(l.v);
        // fill sub vec
        for (int iv = 1; iv < g.Size(); ++iv) {
            if (g.Connected(l.v, iv-1) && !Has(visited, iv)) {
                l.sub.push_back(iv);
            }
        }
        if (l.sub.empty()) {
            //cout << string(10, '-') << endl;
            paths.push_back(visited);
l_next:
            // drop last level
            int v = levels.back().v;
            visited.pop_back();
            levels.pop_back();
            //cout << "x: " << v << endl;
            
            if (levels.empty())
                return paths;

            // drop useless levels
            level_t& bl = levels.back();
            //cout << bl.v << " " << bl.sub.size() << endl;
            if (bl.sub[0] == v) {
                //cout << "x" << endl;
                bl.sub.pop_front();
                if (bl.sub.empty())
                    goto l_next;
                else {
                    level_t next;
                    next.v = bl.sub[0];
                    levels.push_back(next);
                }
            }
        } else {
            level_t next;
            next.v = l.sub[0];
            levels.push_back(next);
        }
    }

    return paths;
}

int main()
{
    /* graph format:
     * row: n0 n1 n2 n3 n4
     * col: n1 n2 n3 n4 n5
     */
    graph_t g;
    g.SetSize(6);
    g << 1 << 1 << 0 << 0 << 0
      << 0 << 1 << 1 << 0 << 0
      << 1 << 0 << 1 << 1 << 0
      << 1 << 1 << 0 << 1 << 1
      << 0 << 1 << 1 << 0 << 1;

    path_t p;
    p << 2 << 1 << 3;

    const vector<path_t>& paths = Search(g);

    for (size_t ip = 0; ip < paths.size(); ++ip) {
        path_t path = paths[ip];
        cout << ip+1 << ":\t";

        int idx = 0;
        for (size_t ip = 0; ip < path.size(); ++ip) {
            if (path[ip] == p[idx])
                ++idx;
            if (idx >= p.size())
                break;
        }

        cout << (idx >= p.size() ? "* " : "  ");

        for (size_t iv = 0; iv < path.size(); ++iv) {
            cout << path[iv] << ((iv < (path.size()-1)) ? " -> " : "\n");
        }

    }

    return 0;
}