TopologicalSort

用途

有向非巡回グラフ(DAG)の頂点を線形順序に並べる.

計算量

$ O(V + E) $

Depends

DirectedGraph

使い方

宣言

1
auto res = topologicalSord(g);

resで線形順序に並べられた頂点を得る.

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> topologicalSort(DirectedGraph &_g) {
  vector<int> d, ind(_g.n);
  for (int i = 0; i < _g.n; i++)
    for (auto e : _g.g[i])
      ind[e.to]++;
  queue<int> que;
  for (int i = 0; i < _g.n; i++)
    if (ind[i] == 0)
      que.push(i);
  while (!que.empty()) {
    int now = que.front();
    d.push_back(now);
    que.pop();
    for (auto e : _g.g[now]) {
      ind[e.to]--;
      if (ind[e.to] == 0)
        que.push(e.to);
    }
  }
  return d;
}