acwing 848 有向图的拓扑序列

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std ;
const int N = 1e5 + 10 ;
 
struct edge{
  int from , to ;
  edge(int a,int b){
    from = a ; to = b ; 
  }
};
vector<edge> e[N] ; // 以i开头的边，且记录有终点
int n , m ;//n个点，m条边
vector<int> topp ; //用于记录拓扑排序
int t[N] ;//记录每一个点的入读 
queue<int> q ;
int main(){
  cin >> n >> m ;
  for(int i = 0 ; i < m ; i ++){
    int a , b ; cin >> a >> b ;
    e[a].push_back(edge(a,b)) ;//加入边 
    t[b] ++ ;//处理入度 
  }
  for(int i = 1 ; i <= n ; i ++){
    if(!t[i]){//把刚开始入度就是零的点加入队列 
      q.push(i) ;
    }
  }
  while(!q.empty()){
    int now = q.front() ;
    topp.push_back(now) ;//只要进入队列中，那就一定是拓扑排序的一个数
    q.pop();
    for(int i = 0; i < e[now].size() ; i ++){
      int x = e[now][i].from , y = e[now][i].to ;
      t[y] -- ;//把入度就是零的点加入队列
      if(!t[y]){//如果入度为0 就加入队列中
        q.push(y) ;
      }
    }
  }
  if(topp.size() == n){//如果拓扑序列的长度为n  那我们求得序列就是拓扑序列
    for(int i = 0 ; i < n ; i ++){
      cout << topp[i] << " ";
    }
    cout << endl ;
  }else cout << -1 << endl ;
  return 0 ;
}