強連結成分分解(SCC)

1
auto res = scc(g);

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

1
res.contractedGraph = {
2
  {1},
3
  {}
4
}

1
struct scc_return {
2
  vector<vector<int>> contractedGraph;
3
  vector<int> indexToContracted;
4
};
5
scc_return scc(const vector<vector<int>> &_g) {
6
  vector<vector<int>> gg(_g.size()), rg(_g.size()), contracted;
7
  vector<int> comp(_g.size(), -1), order, used(_g.size());
8
  for (int i = 0; i < _g.size(); i++) {
9
    for (auto e : _g[i]) {
10
      gg[i].emplace_back(e);
11
      rg[e].emplace_back(i);
12
    }
13
  }
14
  auto dfs = [&](auto &&self, int idx) {
15
    if (used[idx])
16
      return;
17
    used[idx] = true;
18
    for (int to : gg[idx])
19
      self(self, to);
20
    order.push_back(idx);
21
  };
22
  auto rdfs = [&](auto &&self, int idx, int cnt) {
23
    if (comp[idx] != -1)
24
      return;
25
    comp[idx] = cnt;
26
    for (int to : rg[idx])
27
      self(self, to, cnt);
28
  };
29
  for (int i = 0; i < gg.size(); i++)
30
    if (!used[i])
31
      dfs(dfs, i);
32
  reverse(order.begin(), order.end());
33
  int ptr = 0;
34
  for (int i : order)
35
    if (comp[i] == -1)
36
      rdfs(rdfs, i, ptr), ptr++;
37
  contracted.resize(ptr);
38
  for (int i = 0; i < _g.size(); i++) {
39
    for (auto &to : _g[i]) {
40
      int x = comp[i], y = comp[to];
41
      if (x == y)
42
        continue;
43
      contracted[x].push_back(y);
44
    }
45
  }
46
  for (auto &v : contracted) {
47
    sort(v.begin(), v.end());
48
    v.erase(unique(v.begin(), v.end()), v.end());
49
  }
50
  return {contracted, comp};
51
}