トポロジカルソート

説明

有向グラフ g の位相的順序とは，頂点の順序付け u であって，u[i] から u[j] に辺がある => i < j が成立するものをいう．

与えられたグラフ g の位相的順序を求めるアルゴリズムをトポロジカルソートという．これは深さ優先探索木において後退辺が無ければ可能であり，頂点を閉じる順序の逆順がそれとなる．

計算量

O(V+E)

使い方

const Graph &g

グラフ．

vector<int> &order

トポロジカルソートの結果．意味を持つのは戻り値が true のときに限る．

戻り値

トポロジカルソート可能かどうか．

ソースコード

bool visit(const Graph &g, int v, vector<int> &order, vector<int> &color) {
  color[v] = 1;
  FOR(e, g[v]) {
    if (color[e->dst] == 2) continue;
    if (color[e->dst] == 1) return false;
    if (!visit(g, e->dst, order, color)) return false;
  }
  order.push_back(v); color[v] = 2;
  return true;
}
bool topologicalSort(const Graph &g, vector<int> &order) {
  int n = g.size();
  vector<int> color(n);
  REP(u, n) if (!color[u] && !visit(g, u, order, color))
    return false;
  reverse(ALL(order));
  return true;
}

Verified

• UVA 10305 (Ordering Tasks), 2 MS, -- KB