Day58 图论part08

拓扑排序精讲

拓扑排序看上去很复杂，其实了解其原理之后，代码不难

代码随想录

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        List<List<Integer>> last = new ArrayList<>();
        for(int i = 0; i < n; i++){
            last.add(new ArrayList<>());
        }
        
        int[] inDegree = new int[n];
        
        for(int i = 0; i < m; i++){
            int star = sc.nextInt();
            int end = sc.nextInt();
            inDegree[end]++;
            last.get(star).add(end);
        }
        
        Deque<Integer> queue = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        
        
        for(int i = 0; i < inDegree.length; i++){
            if(inDegree[i] == 0){
                queue.add(i);
                //result.add(i);
            }
        }
        
        while(!queue.isEmpty()){
            int cur = queue.remove();
            result.add(cur);
            
            if(last.get(cur).