一. 题目

二. 理论

• 拓扑排序：有向无环图

• 思路：

• 统计入度, 先将入度为0的点加入队列

• 然后宽搜

• 每次将搜到的子节点的入度减1，若为0说明子节点的父亲都遍历过了，将子节点加入队列

• 最后队列中就是一个拓扑排序(tt==n-1时，此时有n个节点在队列中，存在拓扑序)。

三. 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;

int n, m;

class SingleLinkedList
{
public:
    int h[N], e[N], ne[N], idx;
public:
    static void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    SingleLinkedList()
    {
        idx=0;
        fill(h, h+N, -1);
        fill(e, e+N, 0);
        fill(ne, ne+N, 0);
    }

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

class TopologicalSort
{
public:
    int q[N], d[N], hh, tt;
public:
    TopologicalSort()
    {
        hh=0, tt=-1;
        fill(q, q+N, 0);
        fill(d, d+N, 0);
    }

    bool top_sort()
    {
        for(int i=1;i<=n;++i)
            if(!d[i])
                q[++tt]=i;

        while(hh<=tt)
        {
            int t=q[hh++];
            for(int i=sl.h[t];~i;i=sl.ne[i])//~(-1)==0
            {
                int j=sl.e[i];
                if(--d[j]==0) q[++tt]=j;
            }
        }

        return tt==n-1;
    }
}ts;

int main()
{
    SingleLinkedList::initIO();

    cin>>n>>m;
    while(m--)
    {
        int a, b;
        cin>>a>>b;
        sl.add(a, b);
        ++ts.d[b];
    }

    if(ts.top_sort())
    {
        for(int i=0;i<n;++i)
            cout<<ts.q[i]<<" ";
    }
    else cout<<"-1";
}