2022年兰州理工大学天梯赛校内选拔赛题目 7

2022年兰州理工大学天梯赛校内选拔赛题目 7

7-14 羽毛球比赛 (30 分)

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

输入格式:

第一行输入两个整数N和M，其中N（1≤N≤500）表示参加比赛的人数，M表示举行比赛的场次。
以下M行，每行有两个整数Pi和Pj，表示Pi赢了Pj。

输出格式:

输出比赛排名，排名之间有空格分隔。

注意：输入数据保证一定有符合要求的排名。

输入样例:

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

4 3
1 4
4 3
2 3

输出样例:

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

1 2 4 3

C++代码

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <iostream>
#include <algorithm>#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d",&n)
#define rep(i,a,n) for(int i = a; i <= n ; i++)
#define per(i,a,n) for(int i = n; i>= a; i--)
#define fs first
#define se second
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007  
#define INF 0x3f3f3f3f  
typedef long long ll;
using namespace std;const int N = 5e2 + 10;
int n ,m;
int in[N];	//入度
priority_queue<int, vector<int>, greater<int>> q;
vector<int> edge[N];	//边
vector<int> ans; //拓扑序列int main()
{ios;cin >> n >> m;while(m -- ){int a, b;cin >> a >> b;in[b]++;edge[a].push_back(b);}rep(i, 1, N)if(in[i] == 0) //将入度0的点 入队q.push(i);while(!q.empty()){int p = q.top(); q.pop();	//选入度为0的点，出队ans.push_back(p);for(int i = 0; i < edge[p].size(); i++){int y = edge[p][i];in[y]--;if(in[y] == 0)q.push(y);}}bool temp = false;// if(ans.size() == n)rep(i , 0 , n-1){if(temp) cout << " ";cout << ans[i];temp = true;}return 0;
}