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

View the Project on GitHub kmyk/competitive-programming-library

#include "graph/strongly_connected_components.hpp"

#pragma once #include <functional> #include <utility> #include <vector> #include "graph/transpose_graph.hpp" #include "utils/macros.hpp" /** * @brief strongly connected components decomposition, Kosaraju's algorithm / 強連結成分分解 * @return the pair (the number k of components, the function from vertices of g to components) * @param g is an adjacent list of a digraph * @param g_rev is the transpose graph of g * @note $O(V + E)$ */ std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g, const std::vector<std::vector<int> > & g_rev) { int n = g.size(); std::vector<int> acc(n); { std::vector<bool> used(n); std::function<void (int)> dfs = [&](int i) { used[i] = true; for (int j : g[i]) if (not used[j]) dfs(j); acc.push_back(i); }; REP (i,n) if (not used[i]) dfs(i); reverse(ALL(acc)); } int size = 0; std::vector<int> component_of(n); { std::vector<bool> used(n); std::function<void (int)> rdfs = [&](int i) { used[i] = true; component_of[i] = size; for (int j : g_rev[i]) if (not used[j]) rdfs(j); }; for (int i : acc) if (not used[i]) { rdfs(i); ++ size; } } return { size, move(component_of) }; } std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g) { return decompose_to_strongly_connected_components(g, make_transpose_graph(g)); }

#line 2 "graph/strongly_connected_components.hpp" #include <functional> #include <utility> #include <vector> #line 2 "utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "graph/transpose_graph.hpp" /** * @param g is an adjacent list of a digraph * @note $O(V + E)$ * @see https://en.wikipedia.org/wiki/Transpose_graph */ std::vector<std::vector<int> > make_transpose_graph(std::vector<std::vector<int> > const & g) { int n = g.size(); std::vector<std::vector<int> > h(n); REP (i, n) { for (int j : g[i]) { h[j].push_back(i); } } return h; } #line 7 "graph/strongly_connected_components.hpp" /** * @brief strongly connected components decomposition, Kosaraju's algorithm / 強連結成分分解 * @return the pair (the number k of components, the function from vertices of g to components) * @param g is an adjacent list of a digraph * @param g_rev is the transpose graph of g * @note $O(V + E)$ */ std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g, const std::vector<std::vector<int> > & g_rev) { int n = g.size(); std::vector<int> acc(n); { std::vector<bool> used(n); std::function<void (int)> dfs = [&](int i) { used[i] = true; for (int j : g[i]) if (not used[j]) dfs(j); acc.push_back(i); }; REP (i,n) if (not used[i]) dfs(i); reverse(ALL(acc)); } int size = 0; std::vector<int> component_of(n); { std::vector<bool> used(n); std::function<void (int)> rdfs = [&](int i) { used[i] = true; component_of[i] = size; for (int j : g_rev[i]) if (not used[j]) rdfs(j); }; for (int i : acc) if (not used[i]) { rdfs(i); ++ size; } } return { size, move(component_of) }; } std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g) { return decompose_to_strongly_connected_components(g, make_transpose_graph(g)); }