拓扑排序

定义：

拓扑排序指的是有向无环图所有顶点的线性序列

该序列需满足俩个条件：

• 每个顶点只出现一次
• 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面

有向无环图（DAG图）才有拓扑排序，且可能不止一种排序，其他的无拓扑排序一说

应用

拓扑排序通常用来“排序”具有依赖关系的任务。

比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

实现

拓扑排序的建图采用邻接链表的方式，可以手动数字模拟也可以使用vector来直接实现

先找出所有的入度为0的点，让其入队列，然后对队列的元素进行操作：取队首赋给now，扔队首，让now所有的后继节点的入度减1，如果减到了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 100000 + 50
#define endl '\n'
#define mod 13331
#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 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;}


int n, m, a, b, now;
vector<int>in;
vector<vector<int>>ma;//建图

int main(){
    io;
    while (cin>>n>>m && (n + m)) {
        ma = vector<vector<int>>(n + 1);//初始化
        in = vector<int>(n + 1);//初始化
        for(int i = 1; i <= m; ++i){
            cin>>a>>b;
            ma[a].push_back(b);//a->b
            ++in[b];//b的入度加1
        }
        queue<int>q;
        for(int i = 1; i <= n; ++i)if(!in[i])q.push(i);
        while (!q.empty()){
            now = q.front();q.pop();
            cout<<now<<' ';
            for(int i = 0; i < ma[now].size(); ++i){
                in[ma[now][i]]--;
                if(!in[ma[now][i]])q.push(ma[now][i]);
            }
        }
        cout<<endl;
    }
    return 0;
}

• 采用邻接链表来实现

用一个tr结构体来存边的后继节点和next“指针”（指向下一个边的下标）

用in数组来记录点的入度

用head数组来记录每个点作为边的前继节点时最后一次出现的边的下标

用一个队列来放入度为0的点的下标，⚠️要注意这里放的是点的下标

有的时候可能需要字典序排序，那我们就可以使用优先队列来代替队列

手动模拟：

现在我来展示一下head数组和next指针的用法：

假如现在有三条边1->2, 2->3, 3->4

输入1->2时，进行建图，这是第一条边，所以tot为1，tr[1].to = 2，表示边1的后继节点为2，tr[1].next = head[1] = – 1（初始化为-1），此时更新head[1] = 1， in[2] = 1(更新入度)

输入2->3时，继续建图，这是第二条边了，所以tot = 2，tr[2].to = 3, tr[2].next = head[1] = 1,这个时候我们发现以1为前继节点的边2 的next值其实是以1为前继节点的第一条边的下标1，更新head[1]= 2，in[3] = 1

输入3->4时，继续建图，这是第三条边了，所以tot = 3，tr[3].to = 4, tr[3].next = head[1] = 2, 同样的，以1为前继节点的边3的next值其实是第二条以1为前继节点的边2的下标，更新head[1] = 3, in[4] = 1

当我们对点1进行去边时，就可以进行循环，我们要利用tr[1].next = -1 作为结束条件，再利用其他的next作为索引，来循环找上一个的以点1为前继节点的边，也就是我们先让i = head[1] 也就是i = 3，就获得了以点1为前继节点的第一个边的索引（这个第一指的是从后往前的顺序），对这个边进行一系列操作后，我们就需要去找以点1为前继节点的下一个边，就可以利用当前的边的next值，我们就让i = tr[i].next ， 也就是i = 2，获得了下一个边的下标，这时我们就可以去对边2进行操作，同样的再利用第二个边的next值，得到i = 1，继续对边1进行操作，此时tr[i].next = -1 ,说明再没有边是以1为前继节点了，就可以停止了

总的来说，next记录的是上一个以点u为前继节点的边的下标，我们对边进行操作的时候，是从head[u]开始，对当前边进行操作后，利用next获得下一个边的下标，对下一个边进行操作后，再根据这个边的next来获得再下一个边的下标，一环扣一环，就类似于链表的next指针，所以叫做邻接链表，这里插入的方法类似于链表的头插法！

#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 100000 + 50
#define endl '\n'
#define mod 13331
#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 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;}

int n, m, tot, now, a, b;
int head[105];
int in[105];

struct ran{
    int to, next;
}tr[105];

queue<int>q;

void add(int u, int v){
    tr[++tot].to = v;//确定新的边的后继节点
    tr[tot].next = head[u];//确定新的边的上一个边的下标
    head[u] = tot;//跟新head数组的值
    ++in[v];//入度加1
}

void init(){//初始化
    mem(in, 0);
    mem(tr, -1);
    mem(head, -1);
    tot = 0;
}

void topo(){
    for(int i = 1; i <= n; ++i)if(!in[i])q.push(i);
    while (!q.empty()) {
        now = q.front();q.pop();
        cout<<now<<' ';
        for(int i = head[now]; i != -1; i = tr[i].next){
            --in[tr[i].to];
            if(!in[tr[i].to])q.push(tr[i].to);
        }
    }
}

int main(){
    io;
    while(cin>>n>>m && (n + m)){
        init();
        for(int i = 1; i <= m; ++i){
                cin>>a>>b;
                add(a, b);
        }
        topo();
        cout<<endl;
    }
    return 0;
}