奖金——Topsort

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10, M = 2e4+10;
int h[N], e[M], ne[M], idx;
int d[N], in[N], cnt;
int n, m;
queue<int> q;
void add(int a, int b)  // 添加一条边a->b
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}bool bfs()
{for(int i = 1; i <= n; i++)if(!in[i]) q.push(i), d[i] = 0;while(q.size()){int u = q.front(); q.pop(); cnt++;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(--in[j] == 0){if(~d[j]){if(d[j] != d[u] + 1) return false;}else d[j] = d[u] + 1;q.push(j);}}}return cnt == n;
}
int main()
{cin >> n >> m;memset(h, -1, sizeof h);for(int i = 1; i <= m; i++){int a, b;cin >> a >> b;add(b, a);in[a]++;}memset(d, -1, sizeof d);bool success = bfs();if(!success){cout << "Poor Xed";return 0;}int ans = 0;for(int i = 1; i <= n; i++)ans += 100 + d[i];cout << ans;
}