1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

template <typename T = int>
struct SCC : Graph<T> {
public:
  using Graph<T>::Graph;
  using Graph<T>::g;
  Graph<T> dag;
  vector<int> comp;
  vector<vector<int>> group;

  void build() {
    // reversed graph
    rg = Graph<T>(g.size());
    for (size_t i = 0; i < g.size(); i++) {
      for (auto &e : g[i]) {
        rg.add_directed_edge(e.to, e.from, e.cost);
      }
    }
    // topological sort labeling
    used.assign(g.size(), false);
    for (size_t i = 0; i < g.size(); i++) dfs(i);
    reverse(order.begin(), order.end());
    // scc labeling
    int cnt = 0;
    comp.assign(g.size(), -1);
    for (auto idx : order) if (comp[idx] == -1) rdfs(idx, cnt), cnt++;
    // build dag
    dag = Graph<T>(cnt);
    for (size_t i = 0; i < g.size(); i++) {
      for (auto &e : g[i]) {
        int from = comp[e.from], to = comp[e.to];
        if (from == to) continue;
        dag.add_directed_edge(from, to, e.cost);
      }
    }
    // grouping scc
    group.resize(cnt);
    for (size_t i = 0; i < g.size(); i++) {
      group[comp[i]].emplace_back(i);
    }
  }

  int operator[](int k) const {
    return comp[k];
  }

private:
  Graph<T> rg;
  vector<int> order;
  vector<bool> used;

  void dfs(int idx) {
    if (used[idx]) return;
    used[idx] = true;
    for (auto &to : g[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt) {
    if (comp[idx] != -1) return;
    comp[idx] = cnt;
    for (auto &to : rg[idx]) rdfs(to, cnt);
  }
};