PTA 校选拔 7

PTA 校选拔 7

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

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

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

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

4 3
1 4
4 3
2 3

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

1 2 4 3

【分析】

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

由于题目的输入数据保证一定有符合要求的排名，意思即为若 a a a赢 b b b，那么一定不存在直接或间接的 b b b赢 a a 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;
}