graph.topological

参考

graph.topological.rs

#[derive(Debug)]
struct Topological(Vec<usize>);

impl Topological {

    fn visit(u: usize, mut used: &mut Vec<bool>, rd: &Vec<Vec<usize>>, mut ord: &mut Vec<usize>) {
        if used[u] { return }
        used[u] = true;
        for &v in rd[u].iter() {
            Self::visit(v, &mut used, &rd, &mut ord);
        }
        ord.push(u);
    }

    fn new(neigh: &Vec<Vec<usize>>) -> Self {
        let n = neigh.len();
        let mut rd = vec![vec![]; n];
        for u in 0..n {
            for &v in neigh[u].iter() {
                rd[v].push(u);
            }
        }
        // sort
        let mut used = vec![false; n];
        let mut ord = vec![];
        for u in 0..n { Self::visit(u, &mut used, &rd, &mut ord); }
        Topological(ord)
    }
}

Example

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