#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int h[N],e[N],ne[N];
int idx;
int n,m;
int inDegree[N]={0};
stack<int> s;
queue<int> res;

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool findPath(){
    //统计入度
    for(int i=1;i<=n;i++)
        for(int p=h[i];p!=-1;p=ne[p])
            inDegree[e[p]]++;

    //将入度为0的点入栈
    for(int i=1;i<=n;i++){
        if(inDegree[i]==0){
            s.push(i);
        }
    }

    //寻找path
    for(int i=0;i<n;i++){
        if(s.empty()) return false;
        int j=s.top();
        s.pop();
        res.push(j);
        for(int p=h[j];p!=-1;p=ne[p]){
            inDegree[e[p]]--;
            if(inDegree[e[p]]==0) s.push(e[p]);
        }
    }

    return true;
}

int main(){
    memset(h,-1,sizeof h);

    cin>>n>>m;

    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    if(findPath())
        while(!res.empty()){
            int i=res.front();
            res.pop();
            cout<<i<<" ";
        }
    else
        cout<<-1;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla