拓扑排序

# 207. 课程表 (opens new window)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            adjacency.add(new ArrayList());
        }
        Queue<Integer> que = new LinkedList<>();
        // 入度表 与 邻接表 赋值
        for(int[] e:prerequisites){
            indegrees[e[0]]++;
            adjacency.get(e[1]).add(e[0]);
        }
        // 入度为0 入队列
        for(int i=0;i<numCourses;i++){
            if(indegrees[i]==0)
                que.add(i);
        }
        while(!que.isEmpty()){
            int pre = que.poll();
            numCourses--;
            for(int cur:adjacency.get(pre)){
                if(--indegrees[cur]==0){
                    que.add(cur);
                }
            }
        }
        return numCourses==0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 310. 最小高度树 (opens new window)

# 851. 喧闹和富有 (opens new window)

← 并查集 0-1BFS→