宽搜bfs （题号：848）

宽搜思想：

1. 创建一个d数组，用来记录每个节点的入度
2. 然后再创建一个伪队列数组。
3. 遍历一次入度为0的点，然后再遍历一次这些点的边集表，让他们各自的入度-1（因为指向它们的弧尾节点，也就是这个刚被遍历的入度为0的点已经从图移入拓扑序列了，也就是图中已经抹去这个节点了），若如果入读建议后该节点的度数变为0，则让他们也进入拓扑序列。
4. 最后检测如果所有点都存在拓扑序列中，则从0依次输出拓扑数组，如果拓扑数组内的元素不等于所有点的点数，则证明刚刚的图中存在环，返回不存在拓扑序列。

//基于宽搜的拓扑排序思想：每次都将度为0的点依次入队列，最后将队列输出则是拓扑排序，若中途发现有环，则不存在拓扑排序。


#include <bits/stdc++.h>
using namespace std;

int n,m;
const int N = 10000001;
int d[N]; // 记录每个节点的入度，用作检测入队的合法性（入度为0才可入队）；
int q[N]; //手动创建一个数组，用来当作队列，存储进去的顺序即是拓扑排序的顺序。


//邻接表结构，数组+链表
struct node{
   int id;
   node* next;
   node(int _id) : id(_id),next(NULL){}
}*head[N];

//邻接表添加节点
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;

    //先遍历一遍所有的点，如果存在入度为0的点，就入队
    for(int i = 1; i <= n ;i++)
        if(d[i]==0) 
            q[++tt] = i;

    //再遍历已经入队的点中他们自己的链表，将链表中每个入队的点的度都减1
    while(hh<=tt){
        int t = q[hh++];
        for(auto p = head[t];p ;p = p->next)
            if(--d[p->id]==0) q[++t] = p->id;
    }

    return tt == n-1;
}


int main(){

    cin >> n, m;
    while(m--){
        int a,b;
        cin >> a >> b;
        add(a,b);
        d[b]++; //给后一点的入度权值+1
    }
    if(!topsort()) cout << -1; //如果不存在拓扑序列就返回-1
        else
        {
            for(int i = 0;i<n;i++)
            {
                cout << q[i] << ' ';      // 遍历输出拓扑序列队
            }
        }

    return 0;
}