graph.topological

参考

graph.topological.cc

struct Topological {
  int N;
  vector<int> L;
  vector<vector<int>> rd;

  Topological(vector<vector<int>>&d) {
    N = d.size();
    rd.resize(N);
    rep (u, N) {
      for (int v : d[u]) {
        rd[v].push_back(u);
      }
    }
    sort();
  }

  vector<bool> used;

  vector<int> sort() {
    L.resize(0);
    used = vector<bool>(N, false);
    rep (i, N) visit(i);
    return L;
  }

  void visit(int u) {
    if (used[u]) return;
    used[u] = true;
    for (int v : rd[u]) {
      visit(v);
    }
    L.push_back(u);
  }
};

Example


using vi = vector<int>;
using vvi = vector<vi>;
int main() {

  /*
   * 0 -> 1
   * 0 -> 2
   * 1 -> 3
   * 2 -> 4
   * 3 -> 4
   */
  vvi d = {
    { 1, 2 },
    { 3 },
    { 4 },
    { 4 },
    {}
  };
  Topological t(d);
  cout << t.L << endl;

  return 0;
}

Example2