法1、在拓扑排序里求dist

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 10010 , M = 20010;

int n , m;
int e[M] , ne[M] , h[N] , idx;
int ans[N] , d[N];
int q[N];

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

bool topsort()
{
    memset(ans , 0x3f , sizeof ans);
    int hh = 0 , tt = -1;
    for(int i = 1 ; i <= n ; i++)
        if(!d[i])
        {
            q[++tt] = i;
            ans[i] = 100;
        }

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)
            {
                q[++tt] = j;
                ans[j] = ans[t] + 1;
            }
        }
    }

    return tt == n - 1;
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);
    while(m--)
    {
        int a , b;
        scanf("%d%d" , &a , &b);
        add(b , a);
        d[a]++;//入度加一
    }

    if(!topsort()) puts("Poor Xed");
    else
    {
        int res = 0;
        for(int i = 1 ; i <= n ; i++)
            res += ans[i];
        cout << res << endl;
    }
    return 0;
}

求完拓扑排序后，在拓扑序的基础上求最长路

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 10010 , M = 20010;

int n , m;
int e[M] , ne[M] , h[N] , idx;
int dist[N] , d[N];
int q[N];

void 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(!d[i])
        {
            q[++tt] = i;
        }

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)
                q[++tt] = j;
        }
    }

    return tt == n - 1;
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);
    while(m--)
    {
        int a , b;
        scanf("%d%d" , &a , &b);
        add(b , a);
        d[a]++;//入度加一
    }

    if(!topsort()) puts("Poor Xed");
    else
    {
        int res = 0;

        for(int i = 1 ; i <= n ; i++) dist[i] = 100;

        for(int i = 0 ; i < n ; i++)
        {
            int t = q[i];
            for(int k = h[t] ; ~k ; k = ne[k])
            {
                int j = e[k];
                dist[j] = max(dist[j] , dist[t] + 1);
            }
        }

        for(int i = 1 ; i <= n ; i++)
            res += dist[i];
        cout << res << endl;
    }
    return 0;
}