字典序最小拓扑排序 - C++ 实现

字典序最小拓扑排序 - C++ 实现

题目描述

给你一个有向无环图（DAG），求它的字典序最小的拓扑排序序列。

输入格式

第一行输入两个整数n,m,表示图中点的数量和边的数量

接下来m行每行两个整数a,b表示一条边从a走向b // n<=1000,m<=10000

C++ 实现内容

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topsort(vector<vector<int>>& graph, vector<int>& indegree) {
    int n = graph.size();
    vector<int> res;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            pq.push(i);
        }
    }
    
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        res.push_back(node);
        
        for (int i = 0; i < graph[node].size(); i++) {
            int next = graph[node][i];
            indegree[next]--;
            if (indegree[next] == 0) {
                pq.push(next);
            }
        }
    }
    
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> graph(n+1);
    vector<int> indegree(n+1, 0);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        indegree[b]++;
    }
    
    vector<int> res = topsort(graph, indegree);
    
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    
    return 0;
}

算法分析

1. 拓扑排序: 我们使用优先队列来实现字典序最小的拓扑排序。优先队列按照从小到大的顺序弹出元素，确保每次选取的节点都是当前可选节点中编号最小的。
2. 入度: 我们使用 indegree 数组来记录每个节点的入度，即指向该节点的边的数量。初始时，入度为 0 的节点会被加入优先队列中。
3. 遍历: 每次从优先队列中取出入度为 0 的节点，并将该节点加入结果序列中。同时，更新该节点所指向的节点的入度，如果入度变为 0，则将该节点加入优先队列中。
4. 重复: 重复步骤 3，直到优先队列为空。

时间和空间复杂度分析

• 时间复杂度: O(V + E)，其中 V 是节点数量，E 是边数量。
• 空间复杂度: O(V + E)，用于存储图和入度信息。

总结

本文介绍了如何使用 C++ 实现字典序最小拓扑排序，并提供了详细的代码示例和算法分析。这种方法利用优先队列的特性来保证排序结果的字典序最小，并通过入度信息来高效地处理节点的依赖关系。