基础课算法模板:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,idx,ne[N],e[N],h[N],st[N],x,y,dist[N];
vector<int> v;
queue<int> q;
void add(int a,int b)
{
    e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool topo()
{
    for(int i = 1 ; i <= n ; i++) if(!dist[i]) q.push(i),v.push_back(i);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(--dist[j] == 0) q.push(j),v.push_back(j);
        }
    }
    return v.size() == n;
}
int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        cin >> x >> y;
        add(x,y);
        dist[y]++;
    }
    if(topo()) {
        for(int x : v) cout << x << " ";
    }
    else cout << "-1" << endl;
    return 0;
}

练习一:洛谷P1113杂物

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int e[N],ne[N],h[N],idx,dist[N],tim[N],a,b,k,n,f[N];
queue<int> q;
void add(int a,int b)
{
    e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
int topo()
{
    for(int i = 1 ; i<=n ;i++) {
        f[i] = tim[i];
        if(dist[i]==0) q.push(i);
    }
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = h[t] ; i!=-1 ; i=ne[i])
        {
            int j = e[i];
            if(--dist[j] == 0) {
                q.push(j);
            }
            f[j] = max(f[j],f[t]+tim[j]);
        } 
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i++) ans = max(ans,f[i]);
    return ans;
}
int main()
{
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i = 1 ; i <= n ; i++) {
        cin >> a >> b ;
        tim[a] = b;
        while(cin >> k,k!=0){
            add(k,a);
            dist[a]++;
        }
    }
    cout << topo() << endl;
    return 0;
}

洛谷P4017最大食物链计数

 **#include <bits/stdc++.h>
using namespace std;
const int N = 50100,M = 1e6+10,p=80112002;
int n,m,a,b,k,e[M],ne[M],h[N],idist[M],odist[M],idx,f[M];
void add(int a,int b)
{
    e[idx] = b;ne[idx] = h[a] ;h[a] = idx++;
}
int topo()
{
    queue<int> q;
    for(int i = 1; i <= n ; i++){
        if(idist[i]==0) q.push(i),f[i] = 1;
    }
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = h[t] ; i != -1; i = ne[i]){
            int j = e[i];
            if(--idist[j]==0)q.push(j);
            f[j] = (f[j]%p + f[t]%p)%p;
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i++) if(odist[i]==0) ans = (ans%p+f[i]%p)%p;
    return ans;
}
int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 1 ;i <= m ; i++){
        cin >> a >> b;
        add(a,b);
        idist[b]++;
        odist[a]++;
    }
    cout << topo() << endl;
    return 0;
}
**