题目描述

给定一个 n个点 m 条边的有向图，点的编号是 1 到 n ，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y) ，x 在 A 中都出现在 y 之前，则称 A是该图的一个拓扑序列。

样例

输入

3 3
1 2
2 3
1 3

输出

1 2 3

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef queue<int> ns;
typedef int I;

const I N = 100010;
I h[N], e[N], ne[N];
I idx;

I d[N];

I n, m;
ns ans;

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

bool topsort()
{
    ns q;
    I tt = -1;

    for(I i = 1; i <= n; i ++)
        if(!d[i])
            q.push(i), tt ++;

    while(q.size())
    {
        I t = q.front();
        ans.push(t);
        q.pop();

        for(I i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            d[j] --;
            if(!d[j]) q.push(j), tt ++;
        }
    }

    return tt == n - 1;
}

I main()
{
    ios::sync_with_stdio(false),cin.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    while(m --)
    {
        I a, b;

        cin >> a >> b;
        add(a, b);

        d[b] ++;
    }

    if(topsort())
    {
        for(I i = 0; i < n; i ++) printf("%d ", ans.front()), ans.pop();
    }
    else puts("-1");

    return 0;
}

看不懂别见怪
若不是error了， typedef 和 define 可能还会跟多， 见谅 ~(￣.￣)~ hh