graph/topological-sort.hpp

• View this file on GitHub
• Last update: 2023-07-29 15:17:26+09:00
• Include: #include "graph/topological-sort.hpp"

Code

vector<int> topologicalSort(const Graph &g) {
  const int n = g.size();
  vector<int> deg(n);
  for(int i = 0; i < n; ++i){
    for(auto &to: g[i]){
      ++deg[to];
    }
  }
  stack<int> st;
  for(int i = 0; i < n; ++i) {
    if(deg[i] == 0){
      st.emplace(i);
    }
  }
  vector<int> res;
  while(!st.empty()) {
    auto p = st.top();
    st.pop();
    res.emplace_back(p);
    for(auto &to: g[p]) {
      if(--deg[to] == 0) st.emplace(to);
    }
  }
  return res;
}

#line 1 "graph/topological-sort.hpp"
vector<int> topologicalSort(const Graph &g) {
  const int n = g.size();
  vector<int> deg(n);
  for(int i = 0; i < n; ++i){
    for(auto &to: g[i]){
      ++deg[to];
    }
  }
  stack<int> st;
  for(int i = 0; i < n; ++i) {
    if(deg[i] == 0){
      st.emplace(i);
    }
  }
  vector<int> res;
  while(!st.empty()) {
    auto p = st.top();
    st.pop();
    res.emplace_back(p);
    for(auto &to: g[p]) {
      if(--deg[to] == 0) st.emplace(to);
    }
  }
  return res;
}

Back to top page