HDU1285 (确定比赛名次)[拓扑排序]

发表于 | 更新于 | 0 Comments | 阅读次数： 165

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1285
题目给定战胜关系，求每队的排名，看起来与POJ3660很像，但前者是求出每队的排名（可能不唯一），后者是判断每一队的排名是否唯一。
这题可以用拓扑排序做，但要特别注意输出的次序是从小到大的，这里把拓扑排序的队列修改为优先队列，就能按顺序输出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
const int maxn = 510;
int n, m;
int ne = 0;
int rank[maxn];
std::vector<int> V[maxn];
std::priority_queue<int, std::vector<int>, std::greater<int> > q;
int ind[maxn];
int main() {
	int u, v;
	while(scanf("%d%d", &n, &m) != EOF) {
		for(int i = 0; i < maxn; i++) V[i].clear();
		ne = 0;
		while(!q.empty()) q.pop();
		memset(ind, 0, sizeof(ind));
		for(int i = 0; i < m; i++) {
			scanf("%d%d", &u, &v);
			V[u].push_back(v);
			ind[v]++;
		}
		for(int i = 1; i <= n; i++)
			if (!ind[i]) {
				q.push(i);
			}
		while(!q.empty()) {
			int now = q.top();
			q.pop();
			rank[ne++] = now;
			for(int i = 0; i < V[now].size(); i++) {
				int v = V[now][i];
				if (!--ind[v]) {
					q.push(v);
				}
			}
		}
		for(int i = 0; i < ne; i++)
			i != ne - 1 ? printf("%d ", rank[i]) : printf("%d\n", rank[i]);
	}
	return 0;
}