algorithm-dev

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub today2098/algorithm-dev

:x: verify/yosupo-scc-strongly_connected_components.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"

#include <iostream>

#include "../algorithm/Graph/Others/strongly_connected_components.hpp"
#include "../algorithm/Graph/Others/topological_sort.hpp"

int main() {
    int n;
    int m;
    std::cin >> n >> m;

    algorithm::SCC scc(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;

        scc.add_edge(a, b);
    }

    auto &&[num, ids] = scc.decompose();
    auto &&sccs = scc.scc(num, ids);
    auto &&dag = scc.directed_acyclic_graph(num, ids);

    algorithm::TopologicalSort ts(num);
    for(int u = 0; u < num; ++u) {
        for(auto v : dag[u]) ts.add_edge(u, v);
    }
    auto &&v = ts.topological_sort();

    std::cout << num << "\n";
    for(auto id : v) {
        std::cout << sccs[id].size() << " ";
        for(auto v : sccs[id]) std::cout << v << " ";
        std::cout << "\n";
    }
}
#line 1 "verify/yosupo-scc-strongly_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"

#include <iostream>

#line 1 "algorithm/Graph/Others/strongly_connected_components.hpp"



/**
 * @brief Strongly Connected Components(強連結成分分解)
 * @docs docs/Graph/Others/strongly_connected_components.md
 */

#include <algorithm>
#include <cassert>
#include <stack>
#include <utility>
#include <vector>

namespace algorithm {

// Strongly Connected Components(強連結成分分解).
class SCC {
    int m_vn;                            // m_vn:=(ノード数).
    std::vector<std::vector<int> > m_g;  // m_g[v][]:=(ノードvの隣接リスト).

public:
    SCC() : SCC(0) {}
    explicit SCC(int vn) : m_vn(vn), m_g(vn) {}

    // ノード数を返す.
    int order() const { return m_vn; }
    // 有向辺を張る.
    void add_edge(int from, int to) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        m_g[from].push_back(to);
    }
    // 有向グラフを強連結成分分解する.return pair of (# of SCCs, SCC id of each nodes). O(|V|+|E|).
    std::pair<int, std::vector<int> > decompose() const {
        int num_sccs = 0;               // num_sccs:=(SCCの数).
        std::vector<int> ids(order());  // ids[v]:=(ノードvが属するSCCのID).
        // ord[v]:=(DFS木におけるノードvの行きがけ順序).
        // low[v]:=(DFS木において,ノードvから葉方向への辺を0回以上,後退辺を高々1回用いて到達できるノードwに対するord[w]の最小値).
        std::vector<int> ord(order(), -1), low(order());
        int now = 0;
        std::stack<int> visited;
        auto dfs = [&](auto self, int u) -> void {
            ord[u] = low[u] = now++;
            visited.push(u);
            for(int to : m_g[u]) {
                if(ord[to] == -1) {
                    self(self, to);
                    low[u] = std::min(low[u], low[to]);
                } else {
                    low[u] = std::min(low[u], ord[to]);
                }
            }
            if(low[u] == ord[u]) {
                while(true) {
                    int v = visited.top();
                    visited.pop();
                    ord[v] = order();  // inf.
                    ids[v] = num_sccs;
                    if(v == u) break;
                }
                num_sccs++;
            }
        };
        for(int v = 0; v < order(); ++v) {
            if(ord[v] == -1) dfs(dfs, v);
        }
        return {num_sccs, ids};
    }
    // 強連結成分ごとに各ノードをグループ分けする.
    std::vector<std::vector<int> > scc() const { return scc(decompose()); }
    std::vector<std::vector<int> > scc(const std::pair<int, std::vector<int> > &p) const { return scc(p.first, p.second); }
    std::vector<std::vector<int> > scc(int num, const std::vector<int> &ids) const {
        assert((int)ids.size() == order());
        std::vector<std::vector<int> > sccs(num);
        for(int v = 0; v < order(); ++v) {
            assert(0 <= ids[v] and ids[v] < num);
            sccs[ids[v]].push_back(v);
        }
        return sccs;
    }
    // 強連結成分から構成されるDAGを取得する.
    std::vector<std::vector<int> > directed_acyclic_graph(const std::pair<int, std::vector<int> > &p) const { return directed_acyclic_graph(p.first, p.second); }
    std::vector<std::vector<int> > directed_acyclic_graph(int num, const std::vector<int> &ids) const {
        assert((int)ids.size() == order());
        std::vector<std::vector<int> > dag(num);
        for(int u = 0; u < order(); ++u) {
            assert(0 <= ids[u] and ids[u] < num);
            for(int v : m_g[u]) {
                assert(0 <= ids[v] and ids[v] < num);
                if(ids[v] == ids[u]) continue;
                dag[ids[u]].push_back(ids[v]);
            }
        }
        for(std::vector<int> &edge : dag) {
            std::sort(edge.begin(), edge.end());
            edge.erase(std::unique(edge.begin(), edge.end()), edge.end());
        }
        return dag;
    }
};

}  // namespace algorithm


#line 1 "algorithm/Graph/Others/topological_sort.hpp"



/**
 * @brief Topological Sort(トポロジカルソート)
 * @docs docs/Graph/Others/topological_sort.md
 */

#line 10 "algorithm/Graph/Others/topological_sort.hpp"
#include <queue>
#line 12 "algorithm/Graph/Others/topological_sort.hpp"

namespace algorithm {

class TopologicalSort {
    int m_vn;                            // m_vn:=(ノード数).
    std::vector<std::vector<int> > m_g;  // m_g[v]:=(ノードvの隣接リスト).

public:
    TopologicalSort() : TopologicalSort(0) {}
    explicit TopologicalSort(size_t vn) : m_vn(vn), m_g(vn) {}

    // ノード数を返す.
    int order() const { return m_vn; }
    // 有向辺を張る.
    void add_edge(int from, int to) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        m_g[from].push_back(to);
    }
    // 有向非巡回グラフに対する任意のトポロジカルソートの解を求める.O(|V|+|E|).
    std::vector<int> topological_sort() const {
        std::vector<int> res;
        res.reserve(order());
        std::vector<int> deg(order(), 0);  // deg[v]:=(ノードvの入次数).
        for(const std::vector<int> &edges : m_g) {
            for(int to : edges) deg[to]++;
        }
        std::queue<int> que;
        for(int i = 0; i < order(); ++i) {
            if(deg[i] == 0) que.push(i);
        }
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            res.push_back(u);
            for(int v : m_g[u]) {
                if(--deg[v] == 0) que.push(v);
            }
        }
        if((int)res.size() != order()) return std::vector<int>();  // 閉路がある場合.
        return res;
    }
    // 考え得るトポロジカルソートの解を数え上げる.ノード数の実用上限目安は20程度.O(N*(2^N)).
    template <typename Type = long long>
    Type count_up() const {
        assert(order() <= 30);
        const int n = order();
        std::vector<int> b(n, 0);  // b[v]:=(ノードvの隣接リストにある行き先ノードの集合).
        for(int v = 0; v < n; ++v) {
            for(int to : m_g[v]) b[v] |= 1 << to;
        }
        std::vector<Type> dp(1 << n, 0);  // dp[S]:=(ノード集合Sにおける解の通り数).
        dp[0] = 1;
        for(int bit = 0; bit < 1 << n; ++bit) {
            for(int i = 0; i < n; ++i) {
                if(!(bit >> i & 1) and !(bit & b[i])) dp[bit | 1 << i] += dp[bit];
            }
        }
        return dp[(1 << n) - 1];
    }
};

}  // namespace algorithm


#line 7 "verify/yosupo-scc-strongly_connected_components.test.cpp"

int main() {
    int n;
    int m;
    std::cin >> n >> m;

    algorithm::SCC scc(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;

        scc.add_edge(a, b);
    }

    auto &&[num, ids] = scc.decompose();
    auto &&sccs = scc.scc(num, ids);
    auto &&dag = scc.directed_acyclic_graph(num, ids);

    algorithm::TopologicalSort ts(num);
    for(int u = 0; u < num; ++u) {
        for(auto v : dag[u]) ts.add_edge(u, v);
    }
    auto &&v = ts.topological_sort();

    std::cout << num << "\n";
    for(auto id : v) {
        std::cout << sccs[id].size() << " ";
        for(auto v : sccs[id]) std::cout << v << " ";
        std::cout << "\n";
    }
}
Back to top page