トポロジカルソート

i < j のとき、頂点jから頂点iには行けない！！になってる

何通りありますか

bitDPで計算できるらしい…

閉路の検出

トポロジカルソートを用いて有向グラフの閉路検出ができます。

ret.size() == v であればトポロジカルソートが可能だった（閉路がなかった）と判断できる。

code:hoge.cpp

// 0-indexの有向グラフの隣接リストを渡すと、頂点の順番が入ったvectorが返されます

vector<int> topologicalsort(const vector<vector<int> > &G) {

const int V = G.size(); // V…頂点の数

// 全ての頂点の入次数を計算する

vector<int> indegree(V, 0);

for (auto &edges : G)

for (auto &v : edges)

// もし入次数0なら、スタックに追加

stack<int> S;

for (int i = 0; i < V; i++)

S.push(i);

// トポロジカル順に頂点を並べる

vector<int> ret;

while (S.size()) {

int s = S.top(); // 入次数0の頂点番号をSに突っ込む

ret.push_back(s);

S.pop();

}

return ret;

}