当前位置：首页 > news >正文

848. 有向图的拓扑序列（BFS应用）

news 来源：原创 2024/5/4 1:43:57

题目所属分类

属于BFS
有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列
时间复杂度 O(n+m) , n表示点数，m 表示边数

原题链接

在这里插入图片描述

代码案例：输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

题解

有向无环图一定存在拓扑序列
本题的意思就是看一看是否为有向无环图如果是就输出这个拓扑序列
因为
一个有向无环图至少存在一个入度为0的点
然后在有向无环图中删掉一个点依旧是有向无环图所以删掉最后全删干净了那么这个就是拓扑序列拓扑序列放在队列中队列里面加入所有入读为0 的点

普及知识

在这里插入图片描述

题解思路

在这里插入图片描述

题解过程

在这里插入图片描述
开始时，图是这样的状态，发现A的入度为 0，所以删除A和A上所连的边，结果如下图：

这时发现B的入度为 0，C的入度为 0，所以删除B和B上所连的边、C和C上所连的边，结果如下图：

这时发现发现D的入度为 0，所以删除D和D上所连的边(如果有就删)，结果如下图：
这时发现发现D的入度为 0，所以删除D和D上所连的边(如果有就删)，结果如下图：

【空】

这时整个图被删除干净，所有能进行拓扑排序。
解题思路

首先记录各个点的入度
然后将入度为 0 的点放入队列
将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1。
如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。

import java.util.*;
public class Main{
    static int N =  100010,n,m,hh,tt,idx;
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int[] q = new int[N];//数组模拟队列
    static int[] d = new int[N];//保存各个点的入度
    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static boolean topsort(){
        hh = 0; tt = -1 ;
        for(int i = 1 ; i <= n ; i++){
            if(d[i] == 0){
                 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] -- ;//删掉t->j 就是使得它的入度-1
                if(d[j] == 0){
                    q[++tt] = j ;//如果减完之后s的入度数为0；就将他插入队列中
                }
            }
        }
         return tt == n - 1; //说明队列中一共进了n个点  所有的点都入队列了
    }

 public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0 ; i < N ; i ++ ){
            h[i] = -1; 
        }
        while(m -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(a,b);
            d[b] ++;
        }
        
        if(topsort()){//判断是否是拓扑序列
             for(int i = 0 ; i < n; i ++ ){  
                 //队列刚好队头删除的点就是我们的拓扑序列，因为我们只是将hh往后面移动，但是它具体前面的值还在，直接输出就行
                System.out.print(q[i] + " ");
            }
        }else{
             System.out.println("-1");
        }
}
 }