为何？因为我们从root结点开始dfs一遍，可以找到所有的必须在这个root结点之后的点，那么我们就满足了拓扑序的规则了，那么我们无论先dfs(u)还是先dfs(v), 都不会违背这个规则（除非有环），那么同时我们只要按照某种合理的方式存储所有这些点，那么他们就是拓扑序了。
什么是合理的方式？栈！考量一个dfs(u), 在它结束该退出时，它代表它的结点u。在dfs递归中，什么点会最先exit？没有后继结点的点（或者后继已入栈的点）！那么把所有点分成两个集合，一个是待处理的点集D，一个是已拓扑排序后的点集A，当且仅当D中某个点没有后继结点（或该后继结点已经加入了点集A中）时，它可以从D转移到A，而dfs的回溯方式，恰恰就自动实现了这样的功能。 结合代码更容易体会。
不需要判环，输出一种拓扑排序（链式前向星法
#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, a, b, tot, now; int head[MAX]; int in[MAX]; bool vis[MAX]; struct ran{ int to, next; }tr[MAX]; stack<int>s; void init(){ mem(in, 0); mem(vis, 0); mem(tr, 0); mem(head, -1); tot = 0; } void built(int u, int v){ tr[++tot].to = v; tr[tot].next = head[u]; head[u] = tot; } void dfs(int u){ vis[u] = 1;//标记一下这个点来过 for(int i = head[u]; i != -1; i = tr[i].next){ int v = tr[i].to; if(!vis[v])dfs(v);//下一个点如果没来过，就dfs下一个点 } s.push(u);//搜完了就入栈 } int main(){ io; while (cin>>n>>m && (n + m)) { init(); for(int i = 1; i <= m; ++i){ cin>>a>>b; built(a, b); ++in[b]; } for(int i = 1; i <= n; ++i){ if(!vis[i])dfs(i); } while (!s.empty()) { cout<<s.top()<<' ';s.pop(); } cout<<endl; } return 0; } 问题2:如何判环？
判环只是在dfs的基础上稍作修改，其最主要的是对vis数组的含义有所扩展，以及对下一个节点进行dfs判断
不判环对vis只代表该点也没有被访问，而现在vis有三个值，-1，0，1. -1代表已经访问过，但不是当前dfs访问的， 1表示访问过，且是当前的dfs访问的，意味着有环（u->v,v->t,t->u），0表示没访问过
dfs返回的是以root为根节点的后续有没有环，所以我们需要对每个点都去跑一遍dfs，当然，如果已经访问过了，就没必要去dfs他了
伪代码
//判断是否有环(true 没有; false 有) bool dfs(u) { 本趟节点标记; for(遍历以u为入弧的定点){ if(是本趟节点）return false; else if(如果没访问过) { if(子节点有环)return false; } } //表示这个节点的到底都没有环 倒着将沿途的节点加入拓扑队列 //因为这是递归的返回,就是到头回来的过程 return true; } bool topoSort(){ for(遍历节点){ if(没访问过）{ if(有环) return false; } } //所有节点都没环 return true; } 两句if 可以合成为 if(没访问过 && 有环)return false;核心代码如下：
bool dfs(int u) { vis[u] = 1; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (vis[v] == 1) return false; if (vis[v] == 0 && !dfs(v)) return false; } vis[u] = -1; s.push(u); return true; } bool topsort(){ mem(vis, 0); for(int i = n; i >= 1; --i){ if(!vis[i]){ if(!dfs(i))return false; } } return true; }如何按照字典序输出呢？
我们输出的时候是通过栈输出的，栈是先进后出，所以要想字典序最小，只需要让大的先进去，小的后进去，所以我们采用邻接链表的方法存图，存完图以后对每一个root节点的后续节点从大到小进行排序，这样dfs的时候，顺着取后继节点的时候就是从大到小。然后我们for循环的时候，也是从n开始到1去循环即可
#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, a, b, cnt; vector<vector<int> >ma; int vis[MAX]; stack<int>s; bool cmp(int x, int y){ return x > y; } bool dfs(int u){ vis[u] = -1; for(int i = 0; i < ma[u].size(); ++i){ if(vis[ma[u][i]] == -1)return false; else if(vis[ma[u][i]] == 0){ dfs(ma[u][i]); } } vis[u] = 1; s.push(u); return true; } bool topsort(){ mem(vis, 0); for(int i = n; i >= 1; --i){//从大的开始 if(!vis[i]){ if(!dfs(i))return false; } } return true; } int main(){ n = IntRead(); m = IntRead(); ma = vector<vector<int> >(n + 1);//初始化 for(int i = 1; i <= m; ++i){ a = IntRead(); b = IntRead(); ma[a].push_back(b); } for(int i = 1; i <= n; ++i){//排序！ sort(ma[i].begin(), ma[i].end(), cmp); } bool p = topsort(); if(p == false)cout<<"IMPOSABLE\n"; else { while (s.size() != 1) { cout<<s.top()<<" "; s.pop(); } cout<<s.top()<<endl; } return 0; } 输出所有的拓扑序列