求闭包

如果一个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);
}