SCC

発端 自分で書いた SCC (強連結成分分解) ライブラリを使っているのですが， これが，AC-library の SCC に比べて，4倍くらい遅いのです． どこが遅いのか調べてみたら，意外なところにもネックがありました． 最初は，主に使っているアルゴリズムのせいだと思ったのです． 深さ優先探索を2回行うアルゴリズム (たとえばここ を参照) を使っていました． AC-library は，Tarjan のアルゴリズム を使っているようなので，合わせれば速くなるだろう，と思って 書きかえました． たしかに速くなったのですが，それでもまだAC-libraryより3倍ほど遅いです． vector<vector<*> > 部分に分けて測定してみたところ，どうも，グラフの情報を設定しているところも 遅い，ということが分かりました． こんな感じのコードなのですが: int N, M; cin >> N >> M; // N は頂点数, M は辺の数 vector<pair<int, int>> edges; for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; // 0-indexed で入力されると仮定 edeges.emplace_back(u, v); } vector<vector<int>> fwd(N); // fwd[i] は，i から直接行ける頂点たち． // (1) for (auto [u, v] : edges) { fwd[u]....