拓扑排序（字典序最小）题解 题目描述 给定一个n个顶点m条边的有向图，输出字典序最小的拓扑排序。若图中存在环，则输出"has circle."。 输入格式 * 第一行两个整数n,m * 接下来m行，每行两个整数u,v表示有向边 输出格式 * 若无环，输出拓扑排序结果 * 有环则输出"has circle." 算法思路 1. Kahn算法：基于BFS的拓扑排序算法 2. 优先队列：使用小根堆保证每次取出当前可访问的最小顶点 3. 环检测：若最终排序结果顶点数≠n，说明存在环 代码实现 复杂度分析 时间复杂度：O(n log n + m) 优先队列操作O(log n) 每个顶点和边各处理一次 空间复杂度：O(n + m)

#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; }