Ordered Graphs, C++ (clang)

Ordered Graphs

//clang 3.7.0

#include <iostream>
#include <iomanip>
#include <valarray>
#include <vector>
#include <cassert>
#include <initializer_list>
#include <type_traits>
#include <set>
#include <queue>
#include <string>
#include <stack>

using namespace std;

#define trace(s)    (cout << endl << s << endl)

////////////////////////////////////////////////////////////////////////////////////////////////////////
// Matrix

// Универсальный итератор, который преобразовывает любой random-access-iterable класс в sequence-iterable-class
// Для использования в range-based for
// Для использования T должен поддерживать [size_t] и size()
// А также тип reference как ссылка на хранимый тип.
// Через контекст можно специализировать итератор для специальных целей (напр в матрице смежности графа).
template <class T, class Context = void, class Enable = void> class for_iter_t {
    T& t;
    size_t pos;
public:
    for_iter_t(T& t) : t(t), pos(0) {}
    typename T::reference operator*() { return t[pos]; }
    bool operator != (const for_iter_t& f) const { assert(&f.t == &t); return pos != t.size(); }
    void operator++() { ++pos; }
};

// А-ля Страуструп: http://www.stroustrup.com/matrix.c
template<typename T, typename Context = void> class slice_iter {
    typedef vector<T> VT;
    VT& v;
    slice s;
    // Вместо T& используем typename vector<T>::reference для совместимости с vector<bool>
    typename VT::reference ref(size_t i) const { return (v)[s.start() + i * s.stride()]; }
    
public:
    typedef T value_type;
    typedef typename VT::reference reference;
    typedef typename VT::const_reference const_reference;
    slice_iter( VT& v, slice s ) : v(v), s(s) {}
    
    // Заменитель конструктора для константных экземпляров. Обычный конструктор "возвратил бы" не const итератор.
    static const slice_iter ct(const VT& v, slice s) { return slice_iter( const_cast<VT&>(v), s ); }
    
    size_t size() const { return s.size(); }
    const_reference operator[](size_t i) const { return ref(i); }
    reference operator[](size_t i) { return ref(i); }
    
    // Для for(:)
    for_iter_t<slice_iter, Context> begin() { return for_iter_t<slice_iter, Context>(*this); }
    for_iter_t<slice_iter, Context> end() { return for_iter_t<slice_iter, Context>(*this); }
    for_iter_t<const slice_iter, Context> begin() const { return for_iter_t<slice_iter, Context>(*this); }
    for_iter_t<const slice_iter, Context> end() const { return for_iter_t<slice_iter, Context>(*this); }
};

template <typename T, typename Context = void>
class matrix {
    size_t _w;
    size_t _h;
    vector<T> _m;
    
public:
    using vec = slice_iter<T, Context>;
    using value_type = vec;
    using reference = vec; // vec это и value_type и reference.
    using const_reference = const vec;
    
    matrix(size_t w, size_t h) : _w(w), _h(h), _m(w * h) {}
    
    matrix(const matrix&) = default;
    
    matrix(initializer_list<initializer_list<T>> l) {
        _h = l.size();
        _w = _h > 0 ? l.begin()->size() : 0;
        _m.resize( _w * _h );
        size_t pos = 0;
        for( initializer_list<T> const& rowList : l ) {
            assert(rowList.size() == _w);
            for( const T& value : rowList) {
                _m[pos] = value;
                pos++;
            }
        }
    }
    
    size_t w() const { return _w; }
    size_t h() const { return _h; }
    
    vec col(size_t x) { return vec( _m, slice(x, _h, _w) ); }
    const vec col(size_t x) const { return vec::ct( _m, slice(x, _h, _w) ); }
    
    vec row(size_t y) { return vec( _m, slice( y * _w, _w, 1) ); }
    const vec row(size_t y) const { return vec::ct( _m, slice( y * _w, _w, 1) ); }
    
    vec operator[] (size_t y) { return row(y); }
    const vec operator[] (size_t y) const { return row(y); }
        
    size_t size() const { return _h; }
    
    // Для for(:)
    for_iter_t<matrix> begin() { return for_iter(*this); }
    for_iter_t<matrix> end() { return for_iter(*this); }
    for_iter_t<const matrix> begin() const { return for_iter(*this); }
    for_iter_t<const matrix> end() const { return for_iter(*this); }
    
    // Вывод в поток
    friend std::ostream& operator << (std::ostream& os, const matrix<T, Context>& m) {
        for( auto row : m ) {
            for (auto x : row ) {
                cout << setw(2) << x << ", ";
            }
            cout << endl;
        }
        cout << "\n\n";
        return os;
    }
};

//////////////////////////////////////////////////////////////////////////////////////////
// Graph base
    struct GraphEdge;
    
    // Свойства различных графов.
    struct GraphTraits {
        static const bool directed = false;
        static const bool acyclyc = false;
        using EdgeType = GraphEdge;
    };
    
    struct DirectedGraphTraits : public GraphTraits {
        static const bool directed = true;
    };
    
    struct DAGTraits : public DirectedGraphTraits {
        static const bool acyclyc = true;
    };
    
    // Ребро графа.
    struct GraphEdge {
        size_t v;
        size_t w;
        GraphEdge(size_t v, size_t w):v(v),w(w){}
    };
    
    // АТД графа
    class Graph {
    public:
        
        using traits = GraphTraits;
        using Edge = traits::EdgeType;
        
        Graph(size_t vertices, bool isDirected);
        // Кол-во вершин
        size_t size() const;
        
        // Кол-во ребер
        size_t edges() const;
        
        // Ориентирован ли граф
         constexpr bool directed() const { return traits::directed; }
        
        // Вставить ребро
        void insert(const Edge&);
        
        // Удалить ребро
        void remove(const Edge&);
        
        // Еть ли ребро {v, w}
        bool edge(size_t v, size_t w) const;
        
        // Итератор по смежным вершинам графа. Для for(:)
        class AdjIter;

AdjIter adjacent(size_t v) const;
    };

// Вывод графа в виде списка смежности.
    template <class G>
    void show(const G& g, ostream& os = cout) {
        os << "v: " << g.size() << endl;
        os << "e: " << g.edges() << endl;
        for( size_t y = 0; y < g.size(); y++ ) {
            os << setw(2) << y << ":";
            for( size_t x : g.adjacent(y) ) {
                os << setw(2) << x << " ";
            }
            os << endl;
        }
        os << endl;
    }
    
    // Оператор вывода графа в ostream.
    template<class G, class T = typename G::Traits>
    typename enable_if< is_base_of<GraphTraits, T>::value, ostream& >::type
    operator << (ostream& os, const G& g) {
        show(g, os);
        return os;
    }

// Вставляет в граф список ребер.
    template <class G>
    void insertEdges( G& g, std::initializer_list<typename G::Edge>&& es) {
        for( auto&& e : es ) {
            g.insert(e);
        }
    }

/////////////////////////////////////////////////////////////////////////////////////////////
// Dense Graph

// Специализация for_iter_t для итерации по смежным вершинам.
// Для контекстов, производных от GraphTraits.
template <class T, class C> class for_iter_t <T, C,
typename enable_if<is_base_of<GraphTraits, C>::value>::type> {
    T& t;
    size_t pos;
public:
    for_iter_t(T& t) : t(t), pos(0) { if(!t[pos]) ++*this; }
    size_t operator*() { return pos; }
    bool operator != (const for_iter_t& f) const { assert(&f.t == &t); return pos != t.size(); }
    void operator++() { while(++pos < t.size() && t[pos] == false); }
};

///////////////////////////////////////
    // Граф на матрице смежности.
    template<typename GT = GraphTraits>
    class DenseGraph_T {
        using AdjMatrix = matrix<bool, GT>;
        AdjMatrix _adj;
        size_t _edges = 0;
        
    public:
        using Traits = GT;
        using Edge = typename Traits::EdgeType;
        
        DenseGraph_T(size_t v) : _adj(v, v) {}
        
        // Конструктор от другого графа.
        template<class G> DenseGraph_T ( const G& g,
            typename enable_if<is_base_of<GraphTraits, typename G::Traits>::value>::type* = 0 ) : _adj(g.size(), g.size())
        {
            for ( size_t v = 0; v < g.size(); v++ )
                for( size_t w = 0; w < g.size(); w++ )
                    if ( g.edge(v, w) ) {
                        _adj[v][w] = true;
                        _edges++;
                    }
        }
        
        size_t size() const { return _adj.h(); }
        size_t edges() const { return _edges; }
        
        constexpr bool directed() const { return Traits::directed; }
        
        void insert(const Edge& e) {
            size_t v(e.v), w(e.w);
            if(!directed() && v == w) return;
            auto x = _adj[v][w];
            if (!x) {
                _edges++;
                x = true;
            }
            assert(edge(v,w));
            if( !directed() ) _adj[w][v] = true;
        }
        
        void remove(Edge e) {
            size_t v(e.v), w(e.w);
            auto x = _adj[v][w];
            if (x) _edges--;
            x = false;
            assert(!edge(v,w));
            if( !directed() ) _adj[w][v] = false;
        }
        
        bool edge(size_t v, size_t w) const { return _adj[v][w]; }
                
        using AdjIter = typename AdjMatrix::vec;
        
        AdjIter adjacent(size_t v) const { return _adj[v]; }
        // Итератор смежности по транспонированному графу.
        AdjIter adjacentTranspond(size_t v) const { return _adj.col(v); }
        
        using AdjMethod = decltype(&DenseGraph_T::adjacent);
    };
    
    using DenseGraph = DenseGraph_T<GraphTraits>;
    using DenseGraphD = DenseGraph_T<DirectedGraphTraits>;
    using DenseDAG = DenseGraph_T<DAGTraits>;

//////////////////////////////////////////////////////////////////////////////////////
// Sparse Graph
    // Граф на списке смежности вершин.
    template<class GT = GraphTraits>
    class SparseGraph_T {
        using AdjList = vector<size_t>;
        using AdjLists = vector<AdjList>;
        AdjLists _adj;
        size_t _edges = 0;
        bool _ready = false;
        
        void prepare_() const {
            const_cast<SparseGraph_T&>(*this).prepare_();
        }
        
        // Сортирует списки смежности и удаляет дубликаты. Вычисляет количество ребер.
        void prepare_() {
            if (_ready) return;
            _edges = 0;
            for( size_t v = 0; v < _adj.size(); v++ ) {
                AdjList& l = _adj[v];
                set<size_t> s(l.begin(), l.end());
                l.clear();
                for( size_t w : s ) {
                    l.push_back(w);
                    if( v < w ) {
                        _edges++;
                    } else if (directed()) {
                        _edges++;
                    }
                }
            }
            _ready = true;
        }

public:
        using Traits = GT;
        using  Edge = typename Traits::EdgeType;
        
        SparseGraph_T(size_t vertices) : _adj(vertices) {}
        
        // Кол-во вершин
        size_t size() const { return _adj.size(); }
        
        // Кол-во ребер
        size_t edges() const { prepare_(); return _edges; }
        
        constexpr bool directed() const { return Traits::directed; }
        
        // Вставка.
        void insert(const Edge& e) {
            size_t v(e.v), w(e.w);
            if ( !directed() && v == w ) {
                return;
            }
            // Необходима приготовление.
            _ready = false;
            _edges++;
            _adj[v].push_back(w);
            if(!directed()) {
                _adj[w].push_back(v);
            }
        }
        
        // Удаление.
        void remove(const Edge& e) {
            prepare_();
            size_t v(e.v), w(e.w);
            AdjList& lv = _adj[v];
            // lower_bound это binary_search на векторах.
            auto pos = lower_bound(lv.begin(), lv.end(), w );
            if( pos != lv.end() ) {
                lv.erase(pos);
                _edges--;
                if( !directed() ) {
                    AdjList& lw = _adj[w];
                    lw.erase(lower_bound(lw.begin(), lw.end(), v));
                }
            }
        }
        
        // Еть ли ребро {v, w}?
        bool edge(size_t v, size_t w) const {
            prepare_();
            const AdjList& l = _adj[v];
            return binary_search(l.begin(), l.end(), w); // На векторах O(log(N))
        }
        
        // Итератор по смежным вершинам графа.
        using AdjIter = AdjList;
        AdjIter adjacent(size_t v) const {
            prepare_();
            return _adj[v];
        }
    };
    
    using SparseGraph = SparseGraph_T<GraphTraits>;
    using SparseGraphD = SparseGraph_T<DirectedGraphTraits>;
    using SparseDAG = SparseGraph_T<DAGTraits>;

////////////////////////////////////////////////////////////////////////////////////////////
// Undirected graphs

// Визуализатор поиска.
    template<typename GraphTraits, typename Enable = void>
    class SearchTrace_T {
        vector<size_t> p; // родители вершин в остовном лесе. -1 - корень дерева.
    public:
        SearchTrace_T( size_t size ) : p(size, -1) {}
        void visit(typename GraphTraits::EdgeType e) {
            size_t v(e.v), w(e.w);
            if ( p[w] == -1 ) p[w] = v;
            for( size_t vp = p[v]; vp != -1; vp = p[vp] ) cout << string(3, ' ');
            cout << "[" << v << ", " << w << "]" << endl;
        }
        void visit (size_t v) {
            cout << v << endl;
        }
        void reset() { p.assign(p.size(), -1); }
    };
    using SearchTrace = SearchTrace_T<GraphTraits>;
    
    ////////////////////////////////////////////////////////////////////////////
    // Обход графа. Параметризуется методом из нижеприведенных классов:
    template <class G, class Method>
    void traverse(G& g, Method& m) {
        vector<bool> c(g.size()); // цвет вершины. 0 - не посещали, 1 - посещали.
        for( size_t v = 0; v < g.size(); v++ ) {
            if( !c[v] ) if(!m(v, c)) break;
        }
    }
    
    ////////////////////////////////////////////////////////////////
    // DFS Method for traverse. Обход в глубину.
    template <class G, class Inspector, class Context = typename G::Traits> class DFS_T {
        const G& g;
        Inspector& i;
    public:
        DFS_T( const G& g, Inspector& i ) : g(g), i(i) { trace("DFS_T undirected"); }
        
        bool operator() (size_t v, vector<bool>& c ) {
            c[v] = true;
            for( size_t w : g.adjacent(v)) {
                if(c[w] == false) {
                    i.visit( {v, w} );
                    (*this)(w, c);
                }
            }
            return true;
        }
    };
    
    // Ускоритель вызова.
    template <class G, class Inspector>
    DFS_T<G, Inspector> DFS( const G& g, Inspector& i ) { return DFS_T<G, Inspector>(g, i); }
    
    /////////////////////////////////////////////////////////////////
    // Connected Components. Связность.
    
    // Визуализатор связных компонент алгоритма SC.
    template <class SC> void SCTrace( ostream& os, const SC& sc ) {
        os << sc.scnt << " strong components\n";
        vector<vector<size_t>> cc(sc.scnt);
        for( size_t v = 0; v < sc.cnt; v++ ) {
            cc[sc.ids[v]].push_back(v);
        }
        for( size_t i = 0; i < cc.size(); i++ ) {
            for ( size_t j = 0; j < cc[i].size(); j++ ) {
                os << cc[i][j] << ", ";
            }
            os << endl;
        }
    };

// Базовый алгоритм для неориентированных графов.
    template <class G, class Context = typename G::Traits, class ForG = void, class ForC = void> class CC_T {
        const G& g;
        size_t cnt;
        size_t scnt;
        vector<size_t> ids;
        
        void ccR(size_t v) {
            ids[v] = scnt;
            for( size_t w : g.adjacent(v) ) {
                if(ids[w] == -1) ccR(w);
            }
        }
        
        void dfsR (size_t v) {
            ccR(v);
            scnt++;
        }
        
        friend void SCTrace<CC_T>(ostream&, const CC_T&);

public:
        CC_T( const G& g) : g(g), cnt(g.size()), ids(g.size(), -1), scnt(0) { trace("CC_T undirected");
            for ( size_t v = 0; v < g.size(); v++ )
                if( ids[v] == -1) dfsR(v);
        }
        
        size_t size() const { return scnt; }
        size_t id(size_t v) const { return ids[v]; }
        bool connected( size_t v, size_t w ) const { return ids[v] == ids[w]; }
    };

// Ускоритель вызова.
    template <class G>
    CC_T<G> CC(const G& g) { return CC_T<G>(g); }

///////////////////////////////////////////////////////////////////////////////////////////
// DirectedGraphs
    
    enum EdgeRole {
        Tree,
        Back,
        Forward,
        Cross
    };

// Визуализатор поиска в ориентированном графе.
    template<class GT>
    class SearchTrace_T<GT, typename enable_if<is_base_of<DirectedGraphTraits, GT>::value>::type> {
        const char* etStr(EdgeRole er) const {
            switch( er ) {
                case Tree:
                    return " tree";
                case Back:
                    return " back";
                case Forward:
                    return " forward";
                default:
                    assert(er == Cross);
                    break;
            };
            return " cross";
        }
        
    public:
        SearchTrace_T( size_t size ) {}
        void visit(typename GT::EdgeType e, size_t depth, EdgeRole er) {
            size_t v(e.v), w(e.w);
            cout << string(depth * 3, ' ') << "[" << v << ", " << w << "]" << etStr(er) << endl;
        }
    };
    using SearchTraceD = SearchTrace_T<DirectedGraphTraits>;
    
    ////////////////////////////////////////////////////////////////////////////
    // Специализация DFS для ориентированных графов. Метод traverse.
    template <class G, class Inspector> class DFS_T<G, Inspector,
    typename enable_if<is_base_of<DirectedGraphTraits, typename G::Traits>::value, typename G::Traits>::type> {
        const G& g;
        Inspector& i;
        vector<size_t> enter; // порядок входов в вершины.
        vector<size_t> leave; // порядок выходов из вершин.
        size_t cnt;
        size_t depth;
    public:
        DFS_T( const G& g, Inspector& i ) : g(g), i(i), enter(g.size(), -1), leave(g.size(), -1), cnt(0), depth(0) {trace("DFS_T directed");}
        
        bool operator() (size_t v, vector<bool>& c ) {
            c[v] = true;
            enter[v] = cnt++;
            depth++;
            for ( size_t w : g.adjacent(v) ) {
                EdgeRole et = Tree;
                if (enter[w] == -1) {
                    assert(c[w] == false);
                    i.visit( {v, w}, depth, et );
                    (*this)(w, c);
                } else {
                    if ( leave[w] == -1 ) {
                        et = Back;
                    } else if ( enter[v] < enter[w] ) {
                        et = Forward;
                    } else et = Cross;
                    i.visit( {v, w}, depth, et );
                }
            }
            leave[v] = cnt++;
            depth--;
            return true;
        }
    };
    
    /////////////////////////////////////////////////////////////////////////////////////
    // TransitiveClosure Warshall. Транзитивное замыкание Уоршелла. Седжвик 19.3
    class TCW {
        // Исходим из предположения, что граф транзитивного замыкания будет очень плотным.
        // Плюс граф на списках смежности не приспособлен для использования с динамической вставкой ребер.
        DenseGraphD tc;
    public:
        TCW (const DenseGraphD& g) : tc(g) { trace("TC Warshall");
            for ( size_t i = 0; i < g.size(); i++ ) {
                tc.insert({i, i});
            }
            for ( size_t i = 0; i < g.size(); i++ ) {
                for ( size_t s = 0; s < g.size(); s++ ) {
                    if( tc.edge(s, i) ) {
                        for( size_t t = 0; t < g.size(); t++ ) {
                            if ( tc.edge(i, t) ) {
                                tc.insert({s, t});
                            }
                        }
                    }
                }
            }
        }
        
        bool reachable( size_t v, size_t w ) const { return tc.edge(v , w); }
        const DenseGraphD& getTC() const { return tc; }
    };
    
    //////////////////////////////////////////////////////////////////////////////////
    // TransitiveClosure - Транзитивное замыкание - построение множества достижимости на основе DFS. Седжвик 19.4
    // O(V(V + E)).
    template <class G, class Context = typename G::Traits> class TC_T {
        const G& g;
        // Исходим из предположения, что граф транзитивного замыкания будет очень плотным.
        // Плюс граф на списках смежности не приспособлен для использования с динамической вставкой ребер.
        DenseGraphD tc;
        
        void dfs_( size_t v, size_t w ) {
            tc.insert({v, w});
            for ( size_t t : g.adjacent(w)) {
                if (!tc.edge(v, t)) dfs_(v, t);
            }
        }
        
    public:
        TC_T( const G& g) : g(g), tc(g.size()) { trace("TC_T DFS");
            for( size_t v = 0; v < g.size(); v++ ) dfs_(v, v);
        }
        
        bool reachable( size_t v, size_t w ) const { return tc.edge(v , w); }
        const DenseGraphD& getTC() const { return tc; }
    };
    
    // Ускоритель вызова.
    template<class G> TC_T<G> TC(const G& g) { return TC_T<G>(g); }

template <class InG, class OutG> void reverseGraph( const InG& i, OutG& o ) {
        for ( size_t v = 0; v < i.size(); v++ ) {
            for ( size_t w : i.adjacent(v) ) {
                o.insert({w, v});
            }
        }
    }

////////////////////////////////////////////////////////////////////////////
    // Сильные компоненты. Специализация CC_T для ориентированных графов. Алгоритм Косарайю. Седжвик 19.10
    template <class G, class C, class ForG> class CC_T<G, C, ForG, typename enable_if<is_base_of<DirectedGraphTraits, C>::value>::type> {
        size_t cnt;
        size_t scnt;
        vector<size_t> ids, leave;
        
        void dsf_( const G& g, size_t v) {
            ids[v] = scnt;
            for( size_t w : g.adjacent(v) )
                if(ids[w] == -1) dsf_(g, w);
            leave[cnt++] = v;
        }
        
        template<class T> friend void SCTrace(ostream&, const T&);
        
    public:
        CC_T( const G& g ) : cnt(0), scnt(0), ids(g.size(), -1), leave(g.size()) { trace("CC_T Kosaraju");
            // Делаем "топсорт" на обращении графа.
            G r(g.size());
            reverseGraph(g, r);
            for ( size_t v = 0; v < r.size(); v++ )
                if( ids[v] == -1) dsf_(r, v);
            
            ids.assign(g.size(), -1);
            vector<size_t> order = leave;
            cnt = scnt = 0;
            
            for ( size_t v = g.size() - 1; v < -1; v-- )
                if ( ids[order[v]] == -1) {
                    dsf_(g, order[v]);
                    scnt++;
                }
        }
        
        size_t size() const { return scnt; }
        size_t id(size_t v) const { return ids[v]; }
        bool connected( size_t v, size_t w ) const { return ids[v] == ids[w]; }
    };
    
    // Сильные компоненты. Специализация CC_T для графа на матрице смежности. Алгоритм Косарайю.
    // Вместо транспонирования графа применяем обращение к транспонированной матрице смежности.
    template <class G, class C> class CC_T<G, C,
    typename enable_if<is_same<G, DenseGraph_T<C>>::value>::type,
    typename enable_if<is_base_of<DirectedGraphTraits, C>::value>::type> {
        
        using Vec = matrix<bool>::vec;
        size_t cnt;
        size_t scnt;
        vector<size_t> ids, leave;
        
        template<typename G::AdjMethod adjMethod>
        void dfs_( const G& g, size_t v) {
            ids[v] = scnt;
            for( size_t w : (g.*adjMethod)(v) )
                if(ids[w] == -1) dfs_<adjMethod>(g, w);
            leave[cnt++] = v;
        }
        
        friend void SCTrace<CC_T>(ostream&, const CC_T&);
        
    public:
        CC_T( const G& g) : cnt(0), scnt(0), ids(g.size(), -1), leave(g.size()) { trace("CC_T Kosaraju adjmatrix");
            // Делаем "топсорт" на обращении графа.
            for ( size_t v = 0; v < g.size(); v++ )
                if( ids[v] == -1) dfs_<&G::adjacentTranspond>(g, v);
            
            ids.assign(g.size(), -1);
            vector<size_t> order = leave;
            cnt = scnt = 0;
            
            // Проходим dfs-ом по вершинам в топологическом порядке.
            for ( size_t v = g.size() - 1; v < -1; v-- ) {
                size_t next = order[v];
                if ( ids[next] == -1) {
                    dfs_<&G::adjacent>(g, next);
                    scnt++;
                }
            }
        }
        
        size_t size() const { return scnt; }
        size_t id(size_t v) const { return ids[v]; }
        bool connected( size_t v, size_t w ) const { return ids[v] == ids[w]; }
    };
    
    ////////////////////////////////////////////////////////////////////////////////////////////////////////
    // Сильные компоненты, алгоритм Тарьяна (Седжвик 19.11).
    template <class G, class C = typename G::Traits> class SCTar_T {
        const G& g;
        size_t cnt; // топологический счетчик посещения вершин.
        size_t scnt; // количество сильных компонент.
        // st - стек вершин сильной компоненты.
        stack<size_t> st;
        // enter[v] - топологический номер вершины. (назначаемый при обходе в глубину).
        // low[v] - минимальный топологический номер вершины, достижимый из v.
        // ids[v] - номер сильной компоненты, в которой находится v.
        vector<size_t> enter, low, ids;
        
        friend void SCTrace<SCTar_T>(ostream&, const SCTar_T&);
        void dfs_ (size_t v) {
            size_t min = enter[v] = low[v] = cnt++;
            st.push(v);
            for (size_t w : g.adjacent(v)) {
                if ( enter[w] == -1 ) dfs_(w);
                if ( low[w] < min ) min = low[w];
            }
            if ( min < low[v]) {
                low[v] = min;
            } else { size_t w;
                do {
                    ids[ w = st.top() ] = scnt; st.pop();
                    low[w] = -1; // очень большое положительное число.
                } while( v != w );
                scnt++;
            }
        }
        
    public:
        SCTar_T( const G& g ) : g(g), cnt(0), scnt(0), enter(g.size(), -1), low(g.size()), ids(g.size()) { trace("SCTar_T");
            for( size_t v = 0; v < g.size(); v++ )
                if( enter[v] == -1 ) dfs_(v);
        }
        
        size_t size() const { return scnt; }
        size_t id(size_t v) const { return ids[v]; }
        bool connected( size_t v, size_t w ) const { return ids[v] == ids[w]; }
    };
    
    // Ускоритель вызова.
    template<class G> SCTar_T<G> SCTar(const G& g) { return SCTar_T<G>(g); }
    
    ////////////////////////////////////////////////////////////////////////////////////////////////////////
    // Сильные компоненты, алгоритм Габова. 1999 (Седжвик 19.12).
    template <class G, class C = typename G::Traits> class SCGab_T {
        const G& g;
        size_t cnt; // топологический счетчик посещения вершин.
        size_t scnt; // количество сильных компонент.
        // st - стек вершин сильной компоненты.
        // path - стек обхода вершин в глубину до первого обратного ребра.
        stack<size_t> st, path;
        // enter[v] - топологический номер вершины. (назначаемый при обходе в глубину).
        // ids[v] - номер сильной компоненты, в которой находится v.
        vector<size_t> enter, ids;
        
        friend void SCTrace<SCGab_T>(ostream&, const SCGab_T&);
        void dfs_ (size_t v) {
            enter[v] = cnt++;
            st.push(v);
            path.push(v);
            for ( auto w : g.adjacent(v) ) {
                if ( enter[w] == -1 ) {
                    dfs_(w);
                } else if ( ids[w] == -1 ) {
                    while ( enter[path.top()] > enter[w] ) {
                        path.pop();
                    }
                }
            }
            if ( path.top() == v ) {
                path.pop();
                size_t w;
                do {
                    w = st.top();
                    ids[w] = scnt;
                    st.pop();
                } while ( w != v );
                scnt++;
            }
        }
        
    public:
        SCGab_T( const G& g ) : g(g), cnt(0), scnt(0), enter(g.size(), -1), ids(g.size(), -1) { trace("SCGab_T");
            for ( size_t v = 0; v < g.size(); v++ )
                if ( enter[v] == -1 ) dfs_(v);
        }
        
        size_t size() const { return scnt; }
        size_t id(size_t v) const { return ids[v]; }
        bool connected( size_t v, size_t w ) const { return ids[v] == ids[w]; }
    };
    
    // Ускоритель вызова.
    template<class G> SCGab_T<G> SCGab(const G& g) { return SCGab_T<G>(g); }

///////////////////////////////////////////////////////////////////////////////////////////////

template <class G> void buildDirGraph(G& g) {
    // Рис. 19.1 Седжвик.
    insertEdges(g, {
        {4, 2}, {11, 12}, {4, 11}, {5, 4},
        {2, 3}, {12, 9}, {4, 3}, {0, 5},
        {3, 2}, {9, 10}, {3, 5}, {6, 4},
        {0, 6}, {9, 11}, {7, 8}, {6, 9},
        {0, 1}, {8, 9}, {8,7}, {7, 6},
        {2, 0}, {10, 12}
    });
}

template <class G> void testDirGraph(G& g) {
    buildDirGraph(g);
    cout << g;
    SearchTraceD s(g.size());
    auto dfs = DFS(g, s);
    traverse(g, dfs);
    auto tc2 = TCW(g).getTC();
    cout << "Transitive closure Warshall:\n" << tc2;
//    cout << "Transitive closure Warshall2:\n" << TCW(tc2).getTC();
    auto tc = TC(g).getTC();
    cout << "Transitive closure DFS:\n" << tc;
//    cout << "Transitive closure DFS2:\n" << TC(tc).getTC();
    
    auto sc = CC(g);
    SCTrace(cout, sc);
    auto scTar = SCTar(g);
    SCTrace(cout, scTar);
    auto scGab = SCGab(g);
    SCTrace(cout, scGab);
}

void testDenseDirGraph() {
    cout << "Dense directed graph:\n";
    DenseGraphD g(13);
    testDirGraph(g);
}

void testSparseDirGraph() {
    cout << "Sparse directed graph:\n";
    SparseGraphD g(13);
    testDirGraph(g);
}

void testDirGraphs() {
    testDenseDirGraph();
    cout << endl;
    testSparseDirGraph();
}

int main()
{
    testDirGraphs();
    return 0;
}


run \| edit \| history \| help	0