graph/topologicalsort.cpp

• View this file on GitHub
• Last update: 2020-10-30 12:18:04+09:00

Verified with

• test/aoj/3208.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct TopologicalSort{
  vector<vector<int>> G;
  vector<int> indeg;
  TopologicalSort(int n):G(n),indeg(n,0){}

  void add_edge(int s,int t){
    G[s].emplace_back(t);
    indeg[t]++;
  }

  vector<int> build(){
    int n=G.size();

    queue<int> que;
    vector<int> used(n,0);
    auto push=[&](int v){
      if(used[v]) return;
      que.emplace(v);
      used[v]=1;
    };

    for(int i=0;i<n;i++)
      if(indeg[i]==0) push(i);

    vector<int> ps;
    while(!que.empty()){
      int v=que.front();que.pop();
      ps.emplace_back(v);
      for(int u:G[v]){
        indeg[u]--;
        if(indeg[u]==0) push(u);
      }
    }

    if(n!=(int)ps.size()) return {};
    return ps;
  }
};
//END CUT HERE
#ifndef call_from_test
#endif

#line 1 "graph/topologicalsort.cpp"

#include <bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct TopologicalSort{
  vector<vector<int>> G;
  vector<int> indeg;
  TopologicalSort(int n):G(n),indeg(n,0){}

  void add_edge(int s,int t){
    G[s].emplace_back(t);
    indeg[t]++;
  }

  vector<int> build(){
    int n=G.size();

    queue<int> que;
    vector<int> used(n,0);
    auto push=[&](int v){
      if(used[v]) return;
      que.emplace(v);
      used[v]=1;
    };

    for(int i=0;i<n;i++)
      if(indeg[i]==0) push(i);

    vector<int> ps;
    while(!que.empty()){
      int v=que.front();que.pop();
      ps.emplace_back(v);
      for(int u:G[v]){
        indeg[u]--;
        if(indeg[u]==0) push(u);
      }
    }

    if(n!=(int)ps.size()) return {};
    return ps;
  }
};
//END CUT HERE
#ifndef call_from_test
#endif

Back to top page