トポロジカルソートの実装をライブラリ化した

過去問埋めしてて、トポロジカルソートで解く問題に当たって面白かった↓。

atcoder.jp

良い機会なので、改めて実装についてまとめておこうと思う。

前提

トポロジカルソートとは、閉路無し有向グラフ(DAG)において、どの頂点もその出力辺の先の頂点より前にくるように並べること。

ようするに、そのグラフの頂点を「実行順序があるタスク」と見た時、先に実行すべきタスクの順に並べることを言う。

1. 各頂点の入次数をカウントしておく
2. 閉路無し有向グラフなら必ず入次数0の頂点があるので、queue に push する
3. 以下の処理を queue が空になるまで繰り返す
   1. queue に入っている頂点を順に取り出し（pop）、今見ている頂点から移動可能な頂点の入次数を -1 する
   2. 入次数が0になった頂点は都度 queue に push する

こうして queue に push された頂点の順序がトポロジカル順序になる

検証用問題

onlinejudge.u-aizu.ac.jp

実装

/**
 * トポロジカルソート
 * 頂点数をV、辺数をEとして O(V+E)
 */
vector<int> topological_sort(const vector<vector<int>>& G){
  const int n=G.size();
  vector<int> in_cnt(n); // 各頂点の入次数
  // 各頂点の入次数をカウント
  for(int v=0; v<n; v++){
    for(auto nv: G[v]){
      in_cnt[nv]++;
    }
  }
  // 入次数が0の頂点を始点としてqueueにpush（同時にresにもpush）
  vector<int> res;
  queue<int> q;
  for(int v=0; v<n; v++){
    if(in_cnt[v]==0){
      q.push(v);
      res.push_back(v);
    }
  }
  // queueに入っている頂点から移動可能な頂点の入次数をデクリメントし、入次数が0になったものをqueueにpush
  while(!q.empty()){
    int v=q.front(); q.pop();
    for(auto nv: G[v]){
      in_cnt[nv]--;
      if(in_cnt[nv]==0){
        q.push(nv);
        res.push_back(nv);
      }
    }
  }
  // reverse(res.begin(), res.end()); // 入次数0の頂点を先頭にしたい場合
  return res;
}

個人的なメモ

頂点 i => j (i < j)という様に辺が与えられて、2点間から計算されるスコアの最高値を求めよ、みたいな問題（上に載せたABC 188 E Peddler がまさにそう）はトポロジカルソートで解く。

この手の問題を dfs で解こうとすると大概TLEになる。（たまにやらかす）それはそうで、1つ頂点が複数の親を持つ可能性があるので、各2点間におけるスコアを求めるには少なくとも入次数0である全ての頂点を始点として dfs する必要がある。つまり頂点数をV、辺数をEとすると計算量は、O( V * (V + E) )になる。

与えられるグラフが木であるなら dfs で問題ないが、上の様な条件では木にならないことに注意する。（木なら各頂点の親の個数は1個以下になる。また辺の数が V-1 個になるので、まず辺数の制約を確認する）