C++代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 10010, M = N * 2;
int h[N], ne[M], e[M], idx;
int q[N];
int d[N];
int n, m;
int bounus[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort(){
    int tt = -1, hh = 0;
    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 != -1; i = ne[i]){
            int j = e[i];
            //初始入度为0的节点t没有bounus，他的上级有一个，如此迭代
            bounus[j] = max(bounus[j], bounus[t] + 1);
            d[j]--; 
            if(d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}

// int temp[N];
// void copy(int des[], int source[]){
//     for(int i = 1; i <= n; ++i)
//         des[i] = source[i];
// }

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        add(b, a);
        d[a]++;
    }
    if(topsort()){
        int res = 0;
        for(int i = 1; i <= n; ++i) res += bounus[i] + 100;
        cout << res << endl;
    }
    else printf("Poor Xed\n");

    return 0;
}