基于BFS

#include <iostream>

using namespace std;

const int N = 100010, M = 100010;

int n, m;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int d[N], q[N];//d[]表示入度，q[]队列

void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    int hh = 0, tt = -1;//为空的队列。hh对头，tt队尾
    for (int i = 1; i <= n; i ++ )//遍历每一个数
        if (!d[i])//入度为0
            q[ ++ tt] = i;//写入对列

    while (hh <= tt)//对列存在
    {
        int t = q[hh ++ ];//取对头并删除对头
        for (auto p = head[t]; p; p = p->next)//遍历t的所有临边
            if ( -- d[p->id] == 0)//如果发现删完t后这个点的入度=0，入队
                q[ ++ tt] = p->id;
    }

    return tt == n - 1;//判断是否为拓扑序列，即所有元素是否都在队列当中，因为队列从0开始
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d[b] ++ ;//维护入度
        add(a, b);
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ )
            printf("%d ", q[i]);
    }

    return 0;
}

基于DFS

#include <iostream>

using namespace std;

const int N = 100010, M = 100010;

int n, m;

struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL){}
}*head[N];

int st[N], q[N], top;//st[] = 0没有被搜过， 1在递归当中， 2被搜过

void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool dfs(int u)
{
    st[u] = 1;
    for(auto q = head[u]; q; q = q->next)
    {
        int j = q->id;
        if(!st[j])
        {
            if(!dfs(j)) return false;// 有环
        }
        else if(st[j] == 1) return false;// 遇到递归当中的1
    } 
    q[top ++] = u;// 回溯之前的就是拓扑排序的逆序
    st[u] = 2;
    return true;
}

bool topsort()
{
    for(int i = 1; i <= n; i ++)// 一定要遍历一遍所有点，以免有单独的点
    {
        if(!st[i] && !dfs(i))
            return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;

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

    if(!topsort()) puts("-1");
    else
    {
        for(int i = n - 1; i >= 0; i --)// 逆序输出
            cout << q[i] << " ";
    }

    return 0;
}