https://www.luogu.org/problem/P2419

题意：

有N头牛,每个牛有一个唯一且不同的能力等级值.然后他们中的两头牛进行M场比赛,并给你这M场的比赛结果.现在的问题是问你有多少头牛可以确定自己的排名了? 如果对于a胜b且b胜c,那么肯定a胜c. 且如果已经知道了a胜的牛数目+比a厉害的牛数目正好==N-1,那么a的排名也肯定可以推出来.

思路：

大体思路如下，具体细节解释见代码注释。

这是一道floyd变形的题目，利用floyed传递闭包。
以每个顶点正向和反向（反向存图）分别遍历一次，就 使用floyed算法 求出该顶点的出度和如度之和。满足 D入 + D出 == N-1，就可以确定其排名。

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#define ll long long int
using namespace std;
const int maxn = 110;int n, m;
int a[maxn][maxn];//a[i][j]记录i和j之间的关系， 1 => i大于等于j。 0 => i小于jvoid floyed()
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)//a[i][j]=1 级别:i>j.  a[i][j]=0 级别:i<j//i>j 或上 i>k & k>j => i>j。  即只要有一种情况成立，则i>j//a[i][j] | a[i][k]&a[k][j] :有一个为0则不可以传递。a[i][j] = a[i][j] | (a[i][k] & a[k][j]);
}int main()
{while (cin >> n >> m){for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)a[i][j] = 0;//a[i][j]=i==j?1:0;for (int i = 0; i < m; i++){int u, v; cin >> u >> v;a[u][v] = 1;}floyed();int degree[maxn];// = { 0 };memset(degree, 0, sizeof(degree));for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (i != j && a[i][j]){degree[i]++;//i可以打败其他牛的个数加一（i可以打败j）degree[j]++;//可以打败j的牛的个数加一（j被i打败）}//循环之后所有的可能都被计算过，即计算过每个点的出度和入度之和//若和为n-1，则排名可以确定，若和不等于n-1，则不可以确定int ans = 0;for (int i = 1; i <= n; i++)if (degree[i] == n - 1)ans++;cout << ans << endl;}return 0;
}

参考

https://xwk.iteye.com/blog/2129415