拓扑排序是指依次输出入度为0的结点，如果所有结点都可以全部输出，则存在拓扑排序

方法1：bfs 根据上面的定义原理每次来找入度为0的结点，令其输出，然后将其指向的结点的入度减1，也就是yxc所谓的“宽搜”，实际上这个宽搜的队列不一定是队，可以是栈也可以是正常数组，只要可以存储入度为0的结点即可

方法2：dfs 深搜可以在深度搜索第一次就访问到当前结点时就直接将其加入到拓扑排序中，也可以在回溯到当前结点时再加入，后者输出的是拓扑排序的逆序，因为当回溯到这个结点时，当前结点所能到达的结点已经全部输出。

• List dfs方法注意1) 判断是否有环
  如果回溯到的当前结点已经在拓扑排序的队列当中说明该图存在环，则无法输出拓扑排序，所以在记录结点访问情况时需要增加一个变量来记录该结点是否在拓扑排序当中，同时也要用两个变量判断该节点是否已经访问或者未被访问

• List dfs方法注意2) 存在多个联通分量
  如果该图中存在多个连通分量的话我们是无法从一个结点开始访问完所有结点，所以需要增加一个函数用for循环每个结点来访问完所有结点
  相当于在bfs中的将入度为零的结点入队操作一个道理

bfs宽度搜索输出拓扑排序
与其说是宽度搜索不如说是正常的每次输出入度为0的结点而已，维护的容器可以用队列也可以用栈也可以用正常的数组
bfs深度搜索输出拓扑排序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
int n ,m;//n点的数量，m边的数量
struct Node{//点结点的结构体
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];//head是一个链表数组，相当于一个链表，每个元素指向他的每条边

int d[N], q[N];//d表示每个点的入度，q表示队列

//头插法插入一个边界点
void add(int a, int b){
    auto p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

bool topsort(){
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++){
        if(!d[i]){//将一开始入度为0的点都入队
            q[++ tt] = i;
        }
    }
    while(hh <= tt){//队列不为空表示还有度为0的点
        int t = q[hh ++];//出队
        for(auto p = head[t]; p; p = p -> next){
            d[p->id] --;
            if(!d[p->id]){
                q[++ tt] = p->id;
            }
        }
    }
    return tt == n-1;
}

int main(){
    scanf("%d%d", &n, &m);
    while(m --){
        int a,b;
        scanf("%d%d", &a, &b);
        d[b] ++;//b点的入度加1
        add(a, b);
    }
    if(!topsort()){
        printf("-1");
    }else{
        for(int i = 0; i < n; i ++){
            printf("%d ",q[i]);
        }
    }
    return 0;
}

基于原始bfs宽度搜索输出拓扑排序的修改：

//bfs
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
int n ,m;//n点的数量，m边的数量
struct Node{//点结点的结构体
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];//head是一个链表数组，相当于一个链表，每个元素指向他的每条边

int d[N], q[N];//d表示每个点的入度，q表示队列
int hh = 0, tt = -1;

//头插法插入一个边界点
void add(int a, int b){
    auto p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

bool topsort(){
    while(hh <= tt){//队列不为空表示还有度为0的点
        int t = q[hh ++];//出队
        for(auto p = head[t]; p; p = p -> next){
            d[p->id] --;
            if(!d[p->id]) q[++ tt] = p->id;
        }
    }
    return tt == n-1;
}

int main(){
    scanf("%d%d", &n, &m);
    while(m --){
        int a,b;
        scanf("%d%d", &a, &b);
        d[b] ++;//b点的入度加1
        add(a, b);
    }

    for(int i = 1; i <= n; i ++)
         if(!d[i]) q[++ tt] = i;//将一开始入度为0的点都入队

    if(!topsort()){
        printf("-1");
    }else{
        for(int i = 0; i < n; i ++){
            printf("%d ",q[i]);
        }
    }
    return 0;
}

dfs深度搜索输出拓扑排序

//dfs
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
int n ,m;//n点的数量，m边的数量
struct Node{//点结点的结构体d
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];//head是一个链表数组，相当于一个链表，每个元素指向他的每条边

int st[N], q[N], top;
//st[]表示每个结点的状态，0代表没被访问过，1代表在当前输出排序中(表示有环)
                            //2代表已经被访问过

// 头插法插入一个边界点
void add(int a, int b){
    auto p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

// 基于dfs(深度搜索)
//宽度搜索不需要回溯，直接根据结点的入度来判断是否能输出，不存在有环的问题
//深度搜索是基于深搜的回溯来输出拓扑排序，会出现环的问题
bool dfs(int u)
{
    st[u] = 1;//表示已经访问过了
    for(auto p = head[u]; p; p = p -> next)
    {
        int j = p -> id;
        if(!st[j])//未被访问过,则递归p(u的第一子节点)
        {
            if(!dfs(j)) return false;
        }
        else if(st[j] == 1) return false;
    }
    q[top ++] = u;
    st[u] = 2;
    return true;
}

//深度搜索一定要再写一个topsort()函数用来判断是否全部结点都输出
bool topsort()
{
    for(int i = 1; i <= n; i ++)
        if(!st[i] && !dfs(i))
            return false;

    return true;
}


int main(){
    scanf("%d%d", &n, &m);
    while(m --){
        int a,b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    if(!topsort()){
        printf("-1");
    }else{
        //for(int i = 0; i < n; i ++)  printf("%d ",q[i]);
        for(int i = n - 1; i >= 0; i --) printf("%d ",q[i]);
    }
    return 0;
}