我们来看看拓扑排序

╰+哭是因爲堅強的太久メ 2023-10-01 15:37 35阅读 0赞

`我们首先来看看百度百科对拓扑序列的解释`

> 拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。 拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

`百度百科给的求的过程，我们一起来了解一下`

> 对于一个给定的有向图，得到其拓扑序列的步骤如下：  
> ①从图中选择一个入度为0的顶点，并输出该顶点；  
> ②从图中删除该顶点及其相关联的有向边，调整被删除有向边的终点的入度（入度减1）；  
> ③重复①和②；  
> ④直到所有顶点均被输出，拓扑序列完成；否则，无拓扑序列。  
> 可以证明，任何一个无环的有向图一定有拓扑序列，有环的有向图则无拓扑序列。

相信大家看了度娘的解释一定清楚了吧，那么我们接下来就把acwing上的一道题拿来练练手！  
我们先看下题目描述：(这道题可以在acwing 上搜索 `有向图的拓扑序列` 来查看额原题额，顺便也把链接放这吧，就是不知道进不进得去，进不去就自己去acwing 上搜索。[有向图的拓扑序列][Link 1])  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16]  
本着下面这个原则，最终成功拿下了！

while(有bug){
        
    	改bug
    	if（accept）break;
    }

`成功拿下的Code`

#include<bits/stdc++.h>
    using namespace std;
    int n, m;
    const int N = 1000010;
    int h[N], ne[N], e[N], idx;
    int d[N];//d数组表示某点的入度
    void add(int a,int b){
        //存储图，以邻接表的方式
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    int q[N];//定义个队列（数组模拟队列），装入度为0的点。 （这也可以不用队列，就看做是个普通的数组也行）
    int topSe(){
        
        int hh = 0, tt = 0;//初始化队头和队尾
        for (int i = 1; i <= n;i++){
        
            if(!d[i]) q[tt++] = i; //把入度为0的点入队
        }
        while(hh<=tt){
        //队列不空就执行下面的
            int t = q[hh++];//取出队头的数，然后将对头的数出队。(这就是数组模拟队列的优点吧)
            for (int i = h[t]; i != -1;i=ne[i]){
        //遍历头结点的出边
                int j = e[i];//获取到达的点
                d[j]--;//将出边能到达的点，把入度减1（就是把边删掉）
                if(d[j]==0){
        //如果结点的入度为0
                    d[j] = d[t] + 1;//距离 在上一个点的距离基础上 +1 
                    q[tt++] = j;//将这个入度为0的点加入队列  
                }
            }
        }
        return tt == n;//队列长度等于n，返回1，否则返回0
    }
    int main(){
        
        memset(h, -1, sizeof(h));//将h数组全部置为-1，（这个看自己的写法，和上面得第20行有关）
        cin >> n >> m;
        for (int i = 0; i < m;i++){
        
            int a, b;
            cin >> a >> b;
            add(a, b);
            d[b]++;//因为是 a -> b ，所以，b 的入度要加 1
        }
        if(topSe()){
        //如果存在拓扑序列，则输出
            for (int i = 0; i <n;i++)//我们可以发现，队列中的入队顺序就是拓扑序列
                cout << q[i] << " ";
            cout << "\n";
        }else  //不存在则输出-1
            cout << "-1\n";
        return 0;
    }

`贴心时刻`  
担心各位老板难以滑动代码，我还特地的准备了图片版！  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!

[Link 1]: https://www.acwing.com/problem/content/description/850/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/35da3dcd0f5147a7bce8742420d770c6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3EudGlhbmN4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/4fdda15203794044b160f71ee1f365f2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3EudGlhbmN4,size_20,color_FFFFFF,t_70,g_se,x_16