[技术交流] 【C++板块提升计划】动态数组――Vector的详细用法【原创】

#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