1

auto res = scc(g);

1
2
3

res.indexToContracted = {
  0,0,1,1,1
}

1
2
3
4

res.contractedGraph = {
  {1},
  {}
}

 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

struct scc_return {
  vector<vector<int>> contractedGraph;
  vector<int> indexToContracted;
};
scc_return scc(const vector<vector<int>> &_g) {
  vector<vector<int>> gg(_g.size()), rg(_g.size()), contracted;
  vector<int> comp(_g.size(), -1), order, used(_g.size());
  for (int i = 0; i < _g.size(); i++) {
    for (auto e : _g[i]) {
      gg[i].emplace_back(e);
      rg[e].emplace_back(i);
    }
  }
  auto dfs = [&](auto &&self, int idx) {
    if (used[idx])
      return;
    used[idx] = true;
    for (int to : gg[idx])
      self(self, to);
    order.push_back(idx);
  };
  auto rdfs = [&](auto &&self, int idx, int cnt) {
    if (comp[idx] != -1)
      return;
    comp[idx] = cnt;
    for (int to : rg[idx])
      self(self, to, cnt);
  };
  for (int i = 0; i < gg.size(); i++)
    if (!used[i])
      dfs(dfs, i);
  reverse(order.begin(), order.end());
  int ptr = 0;
  for (int i : order)
    if (comp[i] == -1)
      rdfs(rdfs, i, ptr), ptr++;
  contracted.resize(ptr);
  for (int i = 0; i < _g.size(); i++) {
    for (auto &to : _g[i]) {
      int x = comp[i], y = comp[to];
      if (x == y)
        continue;
      contracted[x].push_back(y);
    }
  }
  for (auto &v : contracted) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
  }
  return {contracted, comp};
}