基于深度优先搜索dfs

#include <bits/stdc++.h>
using namespace std;

int n,m;
const int N = 10000001;
int st[N]; // dfs遍历情况： 0（没有遍历过），1（正在遍历中），2（已经遍历完成）
int top;
int q[N];

//邻接表结构，数组+链表
struct node{
   int id;
   node* next;
   node(int _id) : id(_id),next(NULL){}
}*head[N];

//邻接表添加节点
void add(int a,int b){
    auto p = new node(b);
    p->next = head[a]; // 顺序不能乱
    head[a] = p;
}

bool dfs(int i){
    st[i] = 1;

    for(auto p = head[i]; p ; p = p->next){
        int j = p->id;
        if(st[j]==0) //如果没有dfs遍历过
        {
            if(dfs(j)==false) return false;   
        }
        else if(st[j]==1) return false;

    }
    q[top ++ ] = i;

    st[i] = 2;
    return true;

}


bool topsort(){
    for(int i = 1;i<=n;i++)
        if(st[i]==0 && dfs(i)==false)  //如果没有dfs遍历过，就遍历，如果有环就直接返回无拓扑flase 
            return false;
    return true;
}

int main(){

    cin >> n >> m ;
    while(m--){
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    if(!topsort()) cout << -1;
    else
    {
        for(int i = n-1; i>=0;i--){
            cout << q[i] << ' ';
        }
    }


    return 0;
}