トポロジカルソート (Kahn)
概要
DAG が与えられたときに、全ての辺が右を向くように頂点を横一列に並べることをトポロジカルソートといいます．
まず，入次数が 0 の頂点 $v$ は列の一番左に追加できます． 次に，$v$ と $v$ から伸びる辺を取り除きます． そのとき入次数が 0 となる頂点は，取り除いてリストの $v$ の末尾に追加できます． この操作を，全ての頂点が取り除かれるまで繰り返します． 下の実装ではリストに追加できる頂点をキューで管理するので幅優先探索の訪問順 (ただ辺の向きの条件を満たす) のような列になります．
これとは別に，深さ優先探索を行う方法 (tsort-dfs.cc) もあります．
計算量
$O(E+V)$
実装
std::vector<int> tsort(const Graph &g) {
int n = g.size(), k = 0;
std::vector<int> ord(n), in(n);
for (auto &es : g)
for (auto &e : es) in[e.dst]++;
std::queue<int> q;
for (int i = 0; i < n; ++i)
if (in[i] == 0) q.push(i);
while (q.size()) {
int v = q.front();
q.pop();
ord[k++] = v;
for (auto &e : g[v])
if (--in[e.dst] == 0) q.push(e.dst);
}
return *std::max_element(in.begin(), in.end()) == 0 ? ord : std::vector<int>();
}