29 const std::size_t n = out.size();
30 const std::size_t UNSEEN =
static_cast<std::size_t
>(-1);
31 std::vector<std::size_t> index(n, UNSEEN), low(n, 0);
32 std::vector<char> on_stack(n, 0);
33 std::vector<std::size_t> tstack;
34 std::vector<std::vector<std::size_t> > comps;
35 std::size_t counter = 0;
37 for(std::size_t root = 0; root < n; ++root) {
38 if(index[root] != UNSEEN)
40 std::vector<std::pair<std::size_t, std::size_t> > call{{root, 0}};
41 index[root] = low[root] = counter++;
42 tstack.push_back(root);
44 while(!call.empty()) {
45 const std::size_t v = call.back().first;
46 std::size_t &k = call.back().second;
47 if(k < out[v].size()) {
48 const std::size_t u = out[v][k++];
49 if(index[u] == UNSEEN) {
50 index[u] = low[u] = counter++;
53 call.emplace_back(u, 0);
54 }
else if(on_stack[u])
55 low[v] = std::min(low[v], index[u]);
58 if(low[v] == index[v]) {
59 std::vector<std::size_t> comp;
67 comps.push_back(std::move(comp));
71 low[call.back().first] = std::min(low[call.back().first], low[v]);
76 std::reverse(comps.begin(), comps.end());
std::vector< std::vector< std::size_t > > fixSystemComponents(const std::vector< std::vector< std::size_t > > &out)
Strongly connected components of a directed graph, in the order in which equations along its edges ca...