题解 | 【模板】拓扑排序

#include <iostream>
#include <vector>
#include <queue>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n,m;
  std::cin >> n >> m;

  std::vector<std::vector<int>> adj(n+1);//邻接表
  std::vector<int> in(n+1);//入度
  for(int i = 0; i < m; i++){
    int u,v;
    std::cin >> u >> v;

    adj[u].push_back(v);//建有向边u->v
    in[v]++;//v的入度+1
  }

  std::vector<int> ans;//拓扑序

  auto topoSort = [&](){
    std::queue<int> q;

    for(int i = 1; i <= n; i++){
      if(in[i] == 0){//入度为0的入队
        q.push(i);
      }
    }

    while(q.size()){
      auto u = q.front();
      q.pop();
      ans.push_back(u);//节点出队时记录，也可放在入队时统计

      for(auto v:adj[u]){
        if(--in[v] == 0){//如果删去当前u->v的边使得v入度为0，那么v也入队列
          q.push(v);
        }
      }
    }
  };

  topoSort();

  if(ans.size() != n){//拓扑排序失败即拓扑序数组大小不等于n(<n)，输出"-1"并return
    std::cout << "-1\n";
    return 0;
  }

  for(int i = 0; i < ans.size(); i++){//拓扑排序成功输出拓扑序
    std::cout << ans[i] << " \n"[i+1==ans.size()];
  }
}