只需要将queue换成priority_queue即可
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> using namespace std; #define inf 0x3f3f3f3f #define MAX 200000 + 50 #define endl '\n' #define seed 13331 #define mod 1000000000 + 7 #define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define mem(a,b) memset((a),(b),sizeof(a)) typedef long long ll ; //不开longlong见祖宗！ //inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} //inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');} inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;} inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');} int n, m, tot, x, y, now; struct ran{ int to, next; }tr[MAX]; int in[1005]; int head[MAX]; bool vis[MAX]; int ans[1005]; int num; priority_queue<int, vector<int>, greater<int> >q;//优先队列 void built(int u, int v){ tr[++tot].to = v; tr[tot].next = head[u]; head[u] = tot; } void topu(){ tot = 0; while (!q.empty()) { now = q.top();q.pop(); if(vis[now])continue; ++tot;//记录数量 vis[now] = 1; ans[++num] = now; for(int i = head[now]; i != -1; i = tr[i].next){ // cout<<tr[i].to; --in[tr[i].to]; if(in[tr[i].to] == 0)q.push(tr[i].to); } } } int main(){ io; n = IntRead(); m = IntRead(); mem(head, -1); mem(tr, -1); for(int i = 1; i <= m; ++i){ x = IntRead(); y = IntRead(); built(x, y); ++in[y]; } for(int i = 1; i <= n; ++i){ if(in[i] == 0){ q.push(i); } } topu(); if(tot == n){//如果输出的数的数量等与n，就说明没有环 for(int i = 1; i <= n; ++i){ i == 1 ? cout<<ans[i] : cout<<' '<<ans[i]; } cout<<endl; } else cout<<"IMPOSABLE\n"; return 0; } dfs版拓扑排序 问题1:之前写拓扑排序都是用的bfs的方法，没寻思dfs还可以写，直到我做了一下oj的1089，判环的时候发现可以用dfs判环，然后我就好奇如何用dfs进行拓扑排序、如何按字典序输出拓扑序列、如何将所有的拓扑序列都输出，发现网上很少有教这些的，就寻思自己写一写，于是就有了这篇博客o(≧v≦)o
刚开始觉得用dfs写拓扑排序很复杂，这他么的dfs能怎么排？
要从入度为0出发么？
如果有多个入度为0的点，每个都dfs一遍么，那他们会不会乱套？
后来学会了以后感觉简直不可思议，真的是奈何自己没文化，一句wc行天下
首先我们讨论一下拓扑排序的性质，对于一个图，他可能会有好多种拓扑排序，但他们满足一个规律：那就是如果存在有向边u->v , 那么结点 u必须排在v之前（前驱）。同时这种性质具有传递性，也就是说如果同时存在v->t, 那么满足u在t之前。同样的，如果u和v两个结点在图中并不满足这种性质，那么谁在前谁在后就无所谓了。正是利用这个规则，我们进行dfs的顺序是无所谓的。