欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
P2419 Cow Contest
【题目来源】
洛谷：[P2419 USACO08JAN] Cow Contest S - 洛谷
【题目描述】
FJ 的 \(N\)（\(1 \leq N \leq 100\)）头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 \(1, 2, \cdots, N\) 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为 \(A\) 的奶牛的编程能力强于编号为 \(B\) 的奶牛（\(1 \leq A, B \leq N\)，\(A \neq B\))，那么她们的对决中，编号为 \(A\) 的奶牛总是能胜出。FJ 想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 \(M\)（\(1 \leq M \leq 4,500\)）轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
【输入】
第一行两个用空格隔开的整数 \(N, M\)。
第 \(2\sim M + 1\) 行，每行为两个用空格隔开的整数 \(A, B\) ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为胜者）。
【输出】
输出一行一个整数，表示排名可以确定的奶牛的数目。
【输入样例】
5 5
4 3
4 2
3 2
1 2
2 5
【输出样例】
2
【算法标签】
《洛谷 P2419 Cow Contest》 #深度优先搜索DFS# #拓扑排序# #Floyd算法# #USACO# #2008#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 105; // 最大顶点数
int n, m; // n: 顶点数, m: 边数
int d[N][N]; // 邻接矩阵，d[i][j]=1表示i可到达j
int ans; // 满足条件的顶点个数/*** 传递闭包算法* 基于Floyd-Warshall思想，计算有向图的可达性* 如果i可到达k，且k可到达j，则i可到达j*/
void floyd()
{// 三重循环，k为中转点for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 如果i可到达k，且k可到达j，则i可到达jif (d[i][k] && d[k][j]){d[i][j] = 1; // 标记i可到达j}}}}
}int main()
{// 输入顶点数和边数cin >> n >> m;// 构建有向图for (int i = 1; i <= m; i++){int x, y;cin >> x >> y;d[x][y] = 1; // 有向边x→y}// 计算传递闭包floyd();// 统计满足条件的顶点个数for (int i = 1; i <= n; i++){int s = 0; // 统计与顶点i有可达关系的顶点数// 计算到达i的顶点数 + i到达的顶点数for (int j = 1; j <= n; j++){s += d[j][i]; // 统计有多少顶点可到达is += d[i][j]; // 统计i可到达多少顶点}// 如果i与其他n-1个顶点都有可达关系，计数加1if (s == n - 1){ans++;}}// 输出满足条件的顶点个数cout << ans << endl;return 0;
}
【运行结果】
5 5
4 3
4 2
3 2
1 2
2 5
2