【模板】拓扑排序

男娘i 2024-03-22 14:37 79阅读 0赞

![在这里插入图片描述][fe3f83bb1a644065af7ed93ce85261b4.png]

import java.util.Scanner;
    import java.util.*;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int point = in.nextInt();
            int side = in.nextInt();
            int[][] arr = new int[side][2];
            for(int i = 0;i<side;i++){
        
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            //存放当前点可以走向哪几个点
            List<List<Integer>> edegs = new ArrayList<>();
            //存最终结果
            List<Integer> res = new ArrayList<>();
            //队列
            Queue<Integer> queue = new LinkedList<>();
            //存放入度
            int[] indeg = new int[point+1];
            //初始化edegs
            for(int i = 0;i<=point;i++){
        
                edegs.add(new ArrayList());
            }
            //添加集合，和入度以方便之后的判断
            for(int[] info : arr){
        
                edegs.get(info[0]).add(info[1]);
                indeg[info[1]]++;
            }
            //判断入度为0的加入队列中
            for(int i = 1;i<indeg.length;i++){
        
                if(indeg[i] == 0){
        
                    queue.offer(i);
                }
            }
            //判断走了多少次
            int visited = 0;
            //判断是否队列为空,不为空判断里面的逻辑
            while(!queue.isEmpty()){
        
                visited++;
                int u = queue.poll();
                res.add(u);
                for(int v : edegs.get(u)){
        
                    indeg[v]--;
                    if(indeg[v]==0){
        
                        queue.offer(v);
                    }
                }
            }
            if(visited == point){
        
                for(int i = 0;i<res.size();i++){
        
                    if(i != res.size()-1){
        
                       System.out.print(res.get(i)+" ");  
                    }else{
        
                        System.out.print(res.get(i));  
                    }
                }
            }else{
        
                System.out.print(-1);
            } 
        }
    }

[fe3f83bb1a644065af7ed93ce85261b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/96922686918a490d8e464b21c7b5c9cb.png