这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这题之后,对拓扑排序有一个比较深的印象。
拓扑排序并不是常规的排序,在图G结构中,如果G是有向无环图(简单可以理解是向量+不能从出发地回到出发地),如果G中包含边(u,v),则节点u在拓扑排序中处于节点v的前面。
可以将图的拓扑排序看作是将图的所有节点在一条水平线上排开,节点之间的有向边都是从左指向右。
也就是说,拓扑排序的输入是一个图结构,输出是一个序列,这个序列的顺序依赖图G中每个节点的先后关系进行排序。
拓扑排序在生活中的例子,就如穿衣服,穿衣服有先后,我们就可以对穿衣服作一个拓扑排序,输出类似于:内衣 -> 裤子 -> 袜子 -> 鞋子 -> ...。
拓扑排序在计算机中的应用比如Makefile文件的依赖关系,再如Linux系统的包依赖管理如apt、yum等。
也就是说,对于这种存在先后依赖关系的逻辑,都可以用拓扑排序来做。
进入正题:
Problem Description
有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3
1 2
2 3
4 3
Sample Output
1 2 4 3
解题思路:
本题中典型的先后依赖,因此用拓扑排序的方法来解。
源代码:G++ 30ms
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
int main()
{
//队伍数量,输赢数量
int team_count, order_count;
//图
vector<int> Graph[1000];
//输的次数(被依赖的次数)
int lose[1000];
//优先级队列
priority_queue <int, vector<int>, greater<int> > prior_q;
int i, j, k;
while (~scanf("%d %d", &team_count, &order_count)) {
//清空图
for (i = 1; i <= team_count; ++i) {
Graph[i].clear();
}
//清空
memset(lose, 0, sizeof(lose));
//输入输赢情况
for (i = 1; i <= order_count; ++i) {
scanf("%d %d", &j, &k);
//
Graph[j].push_back(k);
//k队输的数量(也是被依赖的数量,或者G图中箭头所指的数量)
lose[k]++;
}
//找出没有输记录的队伍(不需要被依赖)
for (i = 1; i <= team_count; ++i) {
if (lose[i] == 0) {
prior_q.push(i);
}
}
int cnt = 0;
//
while (!prior_q.empty()) {
//prior_q里面都是0,所以直接pop
int x = prior_q.top();
prior_q.pop();
//处理完了标记,-1表示已处理
lose[x] = -1;
printf("%d", x);
cnt++;
//如果已经输出到最后一个了,输出换行
if (cnt == team_count) {
printf("\n");
} else {
printf(" ");
}
for (i = 0; i < Graph[x].size(); ++i) {
//依赖减少1
lose[Graph[x][i]]--;
//如果没有依赖了,则放到prior_q里
if (!lose[Graph[x][i]]) {
prior_q.push(Graph[x][i]);
}
}
}
}
}