【图论】拓扑排序｜ 算法详解 从模板到字典序最小拓扑

拓扑排序

越是执着于这默契 越是不见底地犹豫

越是想要不着痕迹 越是怕激起涟漪

越是忽略点点滴滴 越是数不尽

找不到代替品

盼望黑夜的来临 能拥有自己

咳咳 上次写的拓扑排序太过潦草，看着有点惨不忍睹，来重新写一下，真是早知如此何必当初呢

文章目录

• 拓扑排序
• • 概念
  • 拓扑排序的用途
  • 核心思想
  • 图存储方式
  • 考点总结
  • 模板题
  • 例题：闯关游戏

有向无环图 (DAG)，对图中节点排序，满足：若存在一条边u->v 则在序列里面 u 一定出现在 v 的前面。拓扑排序只处理有向图，无向图不能拓扑排序

如果图存在环，则拓扑排序不存在。

概念

拓扑排序的用途

• 判断有向图是否存在环；

• 输出合法的任务先后顺序；

• DAG 上 DP，求解最长路、最短路。

核心思想

普通队列 vs 优先队列（最小堆）

• queue普通队列：输出任意一种合法拓扑序。
• priority_queue<ll,vector<ll>,greater<ll>>最小堆：每次选编号最小的点，输出字典序最小拓扑序列
• 如果不需要字典序最小，只需要任意合法拓扑序，把优先队列替换普通队列

图存储方式

邻接表：vector<vector<ll>> adj(n+1)

​ adj[u]保存 u 可以直接到达的所有节点。

入度数组：vector<ll> ind(n+1,0)，记录每个节点入度。

考点总结

• 判断有向图是否存在环：ans.size() != n / cnt != n，说明存在环，没有拓扑序列。
• 字典序最小拓扑序：使用小根堆 priority_queue<ll,vector<ll>,greater<ll>>。
• 字典序最大拓扑序：使用大根堆（默认优先队列，不加 greater）。
• DAG 上 DP：按拓扑序遍历节点，求 DAG 最长路 / 最短路。保证处理当前点时，它所有前驱节点已经全部算完。

模板题

任意合法序列

【模板】拓扑排序

#include<bits/stdc++.h>
#define ll long long
#define endl '\\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ull unsigned long long
#define fi first
#define se second
#define PLL pair<ll, ll>
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
using namespace std;
const ll N=2e5+10;
int main()
{
IOS
int n,m;
cin>>n>>m;
vector<vector<int>> adj(n+1);
vector<int> ind(n+1,0);
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
ind[v]++;
}
queue<int> q;
for(int i=1;i<=n;i++)
{
if(ind[i]==0)
q.push(i);
}
vector<int> ans;
while(!q.empty())
{
int x=q.front();
q.pop();
ans.push_back(x);
for(auto y:adj[x])
{
ind[y]—;
if(ind[y]==0) q.push(y);
}
}
if(ans.size()!=n)
{
cout<<–1<<endl;
}
else
{
for(int i=0;i<ans.size();i++)
{
if(i)
cout<<" ";
cout<<ans[i];
}
cout<<endl;
}
return 0;
}

例题：闯关游戏

就像这道题目中表明了 要先输出字典序最小的闯关序列

F-闯关游戏_河南萌新联赛2026第（一）场：河南工业大学

//F
#include<bits/stdc++.h>
#define ll long long
#define endl '\\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ull unsigned long long
#define fi first
#define se second
using namespace std;
int main()
{
IOS
ll t;
cin>>t;
while(t—)
{
ll n,m;
cin>>n>>m;
vector<vector<ll>>adj(n+1);
vector<ll>ind(n+1,0);
for (int i=1;i<=m;i++)
{
ll u,v;
cin>>u>>v;
adj[u].push_back(v);//记录线路
ind[v]++;//记录每个顶点的度
}
priority_queue<ll,vector<ll>,greater<ll>> q;
for(int i=1;i<=n;i++)
{
if(ind[i]==0)
{
q.push(i);//用队列来遍历度为0的边
}
}
ll cnt=0;//用来记录删去点的请况以观察是否成环
vector<ll>ans;
while(!q.empty())
{
ll x=q.top();
q.pop();
ans.push_back(x);
cnt++;
for(auto it:adj[x])
{
ind[it]—;
if(ind[it]==0)
{
q.push(it);
}
}
}
if(cnt!=n)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
for(int k=0;k<ans.size();k++)
{
cout<<ans[k]<<" ";
}
cout<<endl;
}
}

//cout<<fixed<<setprecision(x)<< ;
return 0;
}