什么是拓扑排序？ 先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！
拓扑排序说白了其实不太算是一种排序算法，但又像是一种排序（我是不是说了个废话qwq）
他其实是一个有向无环图（DAG, Directed Acyclic Graph的所有顶点的线性序列，该序列需要满足两个条件：
每个节点只能出现一次
若存在一条A到B到路径，则在拓扑序列中A必然出现在B前面
而有向无环图才具有拓扑排序，非DAG图则没有拓扑排序一说
先看一道拓扑排序的水题趴(>_<)
UVa 10305 - Ordering Tasks 题意：有n个任务要做，有m个要求，每个要求有两个数x，y，要求x必须在y之前执行，让你输出一种执行任务的序列
这里窝给出两种方法，一种dfs，一种bfs，两种建图方法，一种邻接链表，一种链式前向星
再看一道稍微有点变化的拓扑排序
1089.拓扑排序 题意：给定一个有向图，若存在环，输出IMPOSABLE，否则输出一行用一个空格隔开的拓扑排序的结果，若存在多个结果，输出字典序最小的。
既需要判断是否有环也需要输出字典序最小的
同样的，窝给出两种方法，一种dfs，一种bfs，来判环以及输出字典序最小
bfs版拓扑排序 问题1:主要思想就是找出所有入度为0的点，给他们扔进队列里面，然后对对列的元素进行如下操作：取队首赋为now，扔队首，遍历now的所有后继节点，并让他们的入度减1，同时进行判断入度是否减到了0，如果到0了，就扔进对列，一直循环到对列为空结束
如果需要按字典序输出，就用优先队列
邻接链表建图：使用vector，注意要每次初始化vector
#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, now; vector<vector<int> >tr; int in[MAX]; queue<int>q; bool vis[MAX]; void topsort(){ for(int i = 1; i <= n; ++i){ if(in[i] == 0)q.push(i);//找到所有入度为0的点，入队 } while (!q.empty()) { now = q.front();q.pop();//取队首，记得pop if(vis[now])continue;//如果访问过就跳过 vis[now] = 1;//没访问就标记一下 cout<<now<<' ';//输出 for(int i = 0; i < tr[now].size(); ++i){ int v = tr[now][i]; --in[v];//入度减一 if(in[v] == 0)q.push(v);//如果入度为0，入队 } } cout<<endl; } int main(){ io; while (cin>>n>>m && (n + m)) { mem(in, 0); mem(vis, 0); tr = vector<vector<int> >(n + 1);//初始化 for(int i = 1; i <= m; ++i){ cin>>a>>b; tr[a].push_back(b);//b为a的后继节点，就无脑塞 ++in[b];//b的入度加一 } topsort(); } return 0; } 链式前向星建图：主要的思想没有变化，只不过用的是链式前向星建图，相当于板子而已，写多了就习惯了，再加上如果怕vector被卡的话就采用链式前向星
#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]; queue<int>q; 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 topsort(){ for(int i = 1; i <= n; ++i){ if(in[i] == 0)q.push(i); } while (!q.empty()) { now = q.front();q.pop(); if(vis[now])continue; vis[now] = 1; cout<<now<<' '; for(int i = head[now]; i != -1; i = tr[i].next){ int v = tr[i].to; --in[v]; if(in[v] == 0)q.push(v); } } cout<<endl; } 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]; } topsort(); } return 0; } 问题2:如何判环呢？
我们只需要记录输出的数字的个数是否等于n即可
如何输出字典序最小呢？