题解

害，拓扑排序怎么能不写个题解

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx, cnt[N];
int q[N];

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

bool topsort()
{
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
    {
        if (cnt[i] == 0) q[ ++ tt] = i;
    }

    // cout << hh << " " << tt << endl;

    while (hh <= tt)
    {
        int u = q[hh ++ ];
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            // cout << j << endl;
            if ( -- cnt[j] == 0) q[ ++ tt] = j;
        }
    }

    if (tt == n - 1) return true;
    else return false;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        cnt[b] ++ ;
    }

    if (!topsort()) cout << "-1" << endl;
    else
    {
        for (int i = 0; i < n; i ++ ) cout << q[i] << " ";
    }

    return 0;
}