题意:有N个比赛队(1≤N≤500),编号依次为1,2,3,...,N 进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。
符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;
分析:拓扑排序,两种方式
- 入度为0,可取。
- 出度为0,可取。
题目要求编号小的队伍在前,那么使用第1种入度为0,可取的方式。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510, INF = 0x3f3f3f3f;
int n, m, p, d[N], ans[N];
vector<int> g[N];
void topsort() {
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 1; i <= n; i++)
if (d[i] == 0) q.push(i);
while (q.size()) {
int u = q.top(); q.pop();
ans[++p] = u;
for (int v : g[u]) {
d[v]--;
if (d[v] == 0) q.push(v);
}
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v), d[v]++;
}
topsort();
for (int i = 1; i < p; i++) printf("%d ", ans[i]);
printf("%d\n", ans[p]);
for (int i = 1; i <= n; i++) g[i].clear();
memset(d, 0, sizeof(d)), p = 0;
}
return 0;
}
标签:1285,P2,HDU,P1,名次,比赛,int,拓扑,排序
From: https://www.cnblogs.com/hellohebin/p/17266147.html