zhi识点

1.有向无环图被称为拓扑图

#include <bits/stdc++.h>
#define N 100010
using namespace std;

int n, m;
int idx, e[N], h[N], ne[N];
int d[N];//存入度

int ans[N];//存拓扑序列
int cnt;//存拓扑序列

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

void topsort()
{
    queue<int> q;

    for(int i = 1; i <= n; ++ i)
        if(!d[i])
        {
            q.push(i);
            ans[cnt ++ ] = i;
        }

    while(!q.empty())
    {
        int t = q.front();
        q.pop();

        for(int i = h[t]; i != -1; i = ne[i])
        {
            if( -- d[e[i]] == 0)
            {
              q.push(e[i]);
              ans[cnt ++ ] = e[i];
            }
        }
    }


    if(cnt != n) cout << -1;
    else 
    {
        for(int i = 0; i < n; ++ i) cout << ans[i] << ' ';
    }
}

int main()
{
    memset(h, -1, sizeof h);//靠，怎么老忘

    scanf("%d%d", &n, &m);
    for (int i = 0, a, b; i < m; ++ i)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b] ++ ;
    }

    topsort();   
}

附：手动O2优化开关