看到 vector 突然想起来一件事情，在这里放一个之前感觉很有趣的程序大家来看看（ debug ）。这不是一个求助！
代码和原始的已经完全不同了，这里是基于复现问题重新编造了一个背景并且把代码写的更简短和清晰得到的，应该可以排除一些不必要的干扰。当然，代码里不一定只有我想要分享的问题，毕竟水平有限，发现了什么问题都可以提
背景很简单，有向图的拓扑排序，但要同时给出节点的“层次”，节点 A 的“层次”定义为至少需要先删除几个节点和与被删除节点相连的边才能使 A 成为自由的，即没有入度的节点。代码如下#include <iostream>
#include <vector>
using namespace std;
struct node{
int id; // 节点的编号
int level; // 节点的层次
node(int id_, int level_): id(id_), level(level_){}
};
vector<node> arrange(const size_t n, const bool* const map, size_t* const in){
vector<node> result; // 保存结果
// 初始化：找到所有无入度的节点，保存进结果。它们具有层次0
for(size_t i = 0; i < n; i++) if(in[i] == 0) result.emplace_back(i, 0);
// 开始实际排序循环，对于已经记录的每一个节点
for(size_t i = 0; i < result.size(); i++){
// 获取当前找到的节点，使用引用避免复制
node& current = result.at(i);
// 对于每一条出边
for(size_t j = 0; j < n; j++) if(map[current.id * n + j] == true){
// 减少终点的入度
in[j]--;
// 如果终点已无入度，将其加入结果，记录其层次
if(in[j] == 0){
result.emplace_back(j, current.level + 1);
}
}
}
// 查找结束，返回结果
return result;
}
int main(){
// 首先输入节点个数
size_t n;
cin >> n;
// 申请空间存储邻接矩阵和入度表并初始化
bool *map = new bool[n * n];
size_t *in = new size_t[n];
for(size_t i = 0; i < n; i++){
for(size_t j = 0; j < n; j++) map[i * n + j] = false;
in[i] = 0;
}
// 接下来输入边数
size_t m;
cin >> m;
int from, to;
for(size_t i = 0; i < m; i++){
// 输入每一条边，格式是从先给出开始节点再给出结束节点
cin >> from >> to;
// 在矩阵中记录并更新入度
map[from * n + to] = true;
in[to]++;
}
// 进行拓扑排序
auto result = arrange(n, map, in);
// 输出结果
for(const auto i: result) cout << '{' << i.id << ", " << i.level << "} ";
// 释放申请的空间
delete[] map;
delete[] in;
return 0;
}
20
25
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
1 2
1 4
2 6
3 8
4 9
5 10
其实有点无聊，还是希望有兴趣的朋友能玩的愉快 | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
楼主
显身卡
发表于 2022-11-22 13:57:06
发表于 2022-11-22 16:38:45
