PTA 校选拔 7-14 羽毛球比赛（拓扑排序）

本文主要是介绍PTA 校选拔 7-14 羽毛球比赛（拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】
宇航员训练基地要举行羽毛球赛，共有 $N$ 名队员参加比赛，他们的编号分别为 $1,2,3,\dots,N$ ，宇航员王明是比赛的总裁判，但是由于电脑故障，比赛排名没有了，幸运的是王明保留有各场比赛的输赢情况，其中， $P_i,P_j)$ 表示 $P_i$ 队员赢了 $P_j$ 队员，现在请你帮王明计算出羽毛球赛的排名。由于排名情况不唯一，编号小的队员排名在前。

【输入格式】
第一行输入两个整数 $N$ 和 $M$ ，其中 $N (1 \leq N \leq 500)$ 表示参加比赛的人数， $M$ 表示举行比赛的场次。
以下 $M$ 行，每行有两个整数 $P_i$ 和 $P_j$ ，表示 $P_i$ 赢了 $P_j$ 。

【输出格式】
输出比赛排名，排名之间有空格分隔。
注意：输入数据保证一定有符合要求的排名。

【输入样例】
在这里给出一组输入。例如：

【输出样例】
在这里给出相应的输出。例如：

1 2 4 3

【分析】

对于输赢关系，我们可以构建一个有向图， $a \to b$ 表示 $a$ 赢 $b$ ，针对本题样例，构建出的有向图如下：

在这里插入图片描述

由于题目的输入数据保证一定有符合要求的排名，意思即为若 $a$ 赢 $b$ ，那么一定不存在直接或间接的 $b$ 赢 $a$ 的条件，即构造出的有向图一定是无环的，因此使用拓扑排序即可找出一个拓扑序，该拓扑序一定是满足赢的人在输的人前面的。

如何使编号小的队员排名在前呢？使用优先队列的小根堆进行拓扑排序即可。

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;const int N = 510, M = 1000010;
int e[M], ne[M], h[N], idx;
int in[N];
int n, m;
vector<int> res;void add(int u, int v)
{e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}void topSort()
{priority_queue<int, vector<int>, greater<int> > Q;for (int i = 1; i <= n; i++)if (!in[i]) Q.push(i);while (Q.size()){auto t = Q.top();Q.pop();res.push_back(t);for (int i = h[t]; ~i; i = ne[i])if (!--in[e[i]]) Q.push(e[i]);}
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m--){int a, b;cin >> a >> b;add(a, b), in[b]++;}topSort();for (int i = 0; i < res.size(); i++)if (i != res.size() - 1) cout << res[i] << ' ';else cout << res[i];return 0;
}