·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接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
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;
}