拓扑排序（字典序最小）题解

题目描述

给定一个n个顶点m条边的有向图，输出字典序最小的拓扑排序。若图中存在环，则输出"has circle."。

输入格式

• 第一行两个整数n,m
• 接下来m行，每行两个整数u,v表示有向边

输出格式

• 若无环，输出拓扑排序结果
• 有环则输出"has circle."

算法思路

1. Kahn算法：基于BFS的拓扑排序算法
2. 优先队列：使用小根堆保证每次取出当前可访问的最小顶点
3. 环检测：若最终排序结果顶点数≠n，说明存在环

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,m,ind[50];
vector<int> a[50];
vector<int> res;
int main(){
    cin >> n >> m;
    for (int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        ind[v]++;
    }
    priority_queue<int,vector<int>,greater<int> > q;
    for (int i=1;i<=n;i++){
        if (ind[i]==0) q.push(i);
    }
    while (!q.empty()){
        int now = q.top();
        q.pop();
        res.push_back(now);
        for (int i=0;i<a[now].size();i++){
            int next=a[now][i];
            ind[next]--;
            if (ind[next]==0) q.push(next);
        }
    }
    if (res.size()!=n){
        cout << "has circle.";
    }else{
        for (int i=0;i<n;i++){
            cout << res[i] << ' ';
        }
    }
    return 0;
}

复杂度分析
时间复杂度：O(n log n + m)
优先队列操作O(log n)
每个顶点和边各处理一次
空间复杂度：O(n + m)