Contents
概要
トポロジカルソート(Topological sort)とは、閉路がない有向グラフにおいて各辺が順方向になるようなソートである。
実装
- ans.length() == |V|の場合、トポロジカルソートに成功している。
- ans.length() < |V|の場合、トポロジカルソートに失敗している
→グラフに閉路が存在する
struct Edge {
int to;
};
using Graph = vector<vector<Edge>>;
// Topological Sort
// O(|E|+|V|)
vector<int> topo_sort(const Graph& G, bool is_one_indexed = false) {
const int n = G.size();
vector<int> num_input(n);
int start = is_one_indexed ? 1 : 0;
// 入次数
for (int i = start; i < n; i++) {
for (auto e : G[i]) {
num_input[e.to]++;
}
}
// 入次数が0のノードをqueueで管理する
queue<int> que;
for (int i = start; i < n; i++) {
if (num_input[i] == 0) {
que.push(i);
}
}
vector<int> ans;
while (!que.empty()) {
auto node = que.front();
que.pop();
ans.push_back(node);
// 頂点の削除
for (auto e : G[node]) {
num_input[e.to]--;
// 行き先の入次数が0になったらqueueに追加
if (num_input[e.to] == 0) {
que.push(e.to);
}
}
}
return ans;
}
トポロジカルソートの数え上げ
bit DPを用います。