题解 | 【模板】拓扑排序

#include <bitset>//--------这是模板题
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
unsigned char du[200009]{0};//-------------标记入度
bitset<200009> bj;//----------标记有这个节点
map<int, vector<int>> hv_map;//-------模拟邻接表
vector<int> ans;//-----------存答案
queue<int> que;//----------bfs用的队列
int main() {
  int n, m;
  cin >> n >> m;
  int a, b;
  while (cin >> a >> b) { // 注意 while 处理多个 case
    hv_map[a].push_back(b);
    hv_map[b].push_back(a);
    du[b]++;
    bj[a] = 1;
    bj[b] = 1;
  }
  b = 0;
  for (int i = 0; i < 200005; i++)
    if (bj[i]){
      b++;
      if (!du[i])
        que.push(i);
    }
  a = 0;
  int x;
  while(!que.empty()){
    x = que.front();
    que.pop();
    a++;
    ans.push_back(x);
    for (int n : hv_map[x]){
      du[n]--;
      if (!du[n])
        que.push(n);
    }
  }
  if (a != b) cout << -1;
  else{
  size_t size = ans.size();
   for (int i = 0; i < size - 1; i++) cout << ans[i] << ' ';
   if (size >= 1)
   cout << ans[size - 1];//-------------最后一个输出不能跟空格我也不知道为什么T_T
  }
}
// 64 位输出请用 printf("%lld")