确定比赛名次 HDU - 1285 （拓扑排序）

题意：有N个比赛队（1≤N≤500），编号依次为1，2，3，...，N 进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；

分析：拓扑排序，两种方式

入度为0，可取。

出度为0，可取。

题目要求编号小的队伍在前，那么使用第1种入度为0，可取的方式。

#include

using namespace std;

typedef long long LL;

const int N = 510, INF = 0x3f3f3f3f;

int n, m, p, d[N], ans[N];

vector g[N];

void topsort() {

priority_queue, greater > 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;

}