求闭包
如果一个cow 我们知道的大于他的人数+知道的小于他的人数 == n-1
那么就可以断定他的排名。
那么,如果A>B,我们就连一条A到B的边。
A能到的节点数+能到A的节点数为n-1就可以了。
也就是求闭包。我们用佛洛依德算法。
代码:
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int max_m = 5000; const int max_n = 110; bool G[max_n][max_n]; int pre[max_n]; int suff[max_n]; int N, M; int main() { scanf("%d %d", &N, &M); for (int i = 1, u, v;i <= M;++i) { scanf("%d %d", &u, &v); G[u][v] = true; }for (int k = 1;k <= N;++k) for (int i = 1;i <= N;++i) for (int j = 1;j <= N;++j) if (G[i][k] && G[k][j]) G[i][j] = true; int ans = 0; for (int i = 1;i <= N;++i) { int tmp = 0; for (int j = 1;j <= N;++j) { tmp += G[i][j]; tmp += G[j][i]; } if (tmp == N - 1)++ans; }printf("%d", ans); }