问题描述：
有N个比赛队伍(1<=N<=500)，编号依次为1,2,3,⋯⋯, N，进行比赛。比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即如果P1赢P2, 用P1 P2表示，排名时P1在P2之前。现在请你编程序确定排名。
输入：输入有若干组，每组中的第一行为二个数N和M其中，N表示队伍的个数，且1<=N<=500,M表示接着有M行的输入数据。接下来的M行数据中，每行包含两个整数P1和P2, 表示P1队赢了P2队。
输出：给出一个符合要求的排名，无法确定名次的队伍输出时编号小的队伍在前。
输入样例：
4 3
1 2
2 3
4 3
输出样例：
1 2 4 3
代码示例👇
//author:Mitchell_Donovan
//date:5.11
#include
#include
using namespace std;
//边类
class Edge {
public:
int from, to, weight;
Edge() {
from = -1;
to = -1;
weight = 0;
}
Edge(int fromValue, int toValue, int weightValue) {
from = fromValue;
to = toValue;
weight = weightValue;
}
};
//图类
class Graph {
public:
int numVertex;
int numEdge;
int* Mark;//标记图中顶点是否被访问过
int* Indegree;//存放图中顶点的入度
Graph(int num) {
numVertex = num;
numEdge = 0;
Indegree = new int[numVertex];
Mark = new int[numVertex];
for (int i = 0; i < numVertex; i++) {
Mark[i] = 0;//0表示未访问过
Indegree[i] = 0;//入度设为0
}
}
~Graph() {
delete[]Mark;
delete[]Indegree;
}
//判断是否为边
bool isEdge(Edge oneEdge) {
if (oneEdge.weight > 0 && oneEdge.weight < INFINITY && oneEdge.to >= 0) {
return true;
}
else {
return false;
}
}
//访问
void Visit(Graph& G, int v) {
cout << v + 1 << " ";
//cout << G.data[v];
}
};
//用相邻矩阵表示图
class Graphm :public Graph {
private:
int** matrix;//指向相邻矩阵的指针
public:
Graphm(int num) :Graph(num) {
matrix = (int**)new int* [numVertex];//申请二维数组空间
for (int i = 0; i < numVertex; i++) {
matrix[i] = new int[numVertex];
}
for (int i = 0; i < numVertex; i++) {//相邻矩阵初始化
for (int j = 0; j < numVertex; j++) {
matrix[i][j] = 0;
}
}
}
~Graphm() {
for (int i = 0; i < numVertex; i++) {
delete[]matrix[i];
}
delete[] matrix;
}
//返回顶点的第一条边
Edge firstEdge(int oneVertex) {
Edge myEdge;
myEdge.from = oneVertex;
for (int i = 0; i < numVertex; i++) {
if (matrix[oneVertex][i] != 0) {
myEdge.to = i;
myEdge.weight = matrix[oneVertex][i];
break;
}
}
return myEdge;
}
//返回与已知边相同顶点的下一条边
Edge nextEdge(Edge preEdge) {
Edge myEdge;
myEdge.from = preEdge.from;
if (preEdge.to >= numVertex) {//不存在下一条边
return myEdge;
}
for (int i = preEdge.to + 1; i < numVertex; i++) {
if (matrix[preEdge.from][i] != 0) {
myEdge.to = i;
myEdge.weight = matrix[preEdge.from][i];
break;
}
}
return myEdge;
}
//为图设置一条边
void setEdge(int from, int to, int weight) {
if (matrix[from][to] <= 0) {//如果原边不存在
numEdge++;
Indegree[to]++;
}
matrix[from][to] = weight;
}
//删除图的一条边
void delEdge(int from, int to) {
if (matrix[from][to] > 0) {//如果原边存在
numEdge--;
Indegree[to]--;
}
matrix[from][to] = 0;
}
//用队列实现图拓扑排序
void TopsortbyQueue(Graphm& G) {
for (int i = 0; i < G.numVertex; i++) {//初始化Mark数组
G.Mark[i] = 0;
}
priority_queue
for (int i = 0; i < G.numVertex; i++) {
if (G.Indegree[i] == 0) {
Q.push(i);
}
}
while (!Q.empty()) {
int v = Q.top();
Q.pop();
Visit(G, v);
G.Mark[v] = 1;
for (Edge e = G.firstEdge(v); G.isEdge(e); e = G.nextEdge(e)) {
G.Indegree[e.to]--;
if (G.Indegree[e.to] == 0) {
Q.push(e.to);
}
}
}
for (int i = 0; i < G.numVertex; i++) {//利用标记位还可判断图中是否有环
if (G.Mark[i] == 0) {
cout << "此图有环！" << endl;
break;
}
}
}
};
int main() {
int N;
cout << "请输入队伍个数：";
cin >> N;
Graphm test(N);
int M;
cout << "请输入比赛场数：";
cin >> M;
for (int i = 1; i <= M; i++) {
int x = 0, y = 0;
cin >> x;
cin >> y;
test.setEdge(x - 1, y - 1, 1);
}
test.TopsortbyQueue(test);
}
补充说明👇
因为本题要求无法确定名次的队伍输出时编号小的队伍在前，所以我们使用了单调队列来进行拓扑排序
c++优先队列(priority_queue)用法详解
运行效果👇
原题相关网站：
http://acm.hdu.edu.cn/listproblem.php?vol=1，
http://acm.hdu.edu.cn/showproblem.php?pid=1285