【Check 67】2024-05-06 - 207. 课程表

[larscheng]

207. 课程表

[larscheng]

思路

拓扑排序+深度遍历

代码

class Solution {
      List<List<Integer>> edges;
      int[] visited;
      boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        visited = new int[numCourses];
        //1,0
        //2,1
        //3,2
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }
        //依次搜索
        for (int i = 0; i < numCourses && valid; i++) {
            //未搜索状态
            if (visited[i]==0){
                dfs(i);
            }
        }
        return valid;
    }

    private void dfs(int i) {
        //搜索中
        visited[i] =1;
        for (Integer target : edges.get(i)) {
            if (visited[target]==0){
                //未搜索，继续dfs
                dfs(target);
                if (!valid){
                    return;
                }
            }else if (visited[target]==1){
                //搜索中，存在环，无拓扑排序
                valid = false;
                return;
            }
        }
        //搜索完成
        visited[i] = 2;
    }
}

复杂度

• 时间复杂度：O(n+m)
• 空间复杂度：O(n+m)