LeetCode_环检测_DFS_中等_207.课程表

ゞ浴缸里的玫瑰 2023-10-06 22:37 38阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 **prerequisites\[i\] = \[ai, bi\] ，表示如果要学习课程 ai 则必须先学习课程 bi。**

例如，先修课程对 \[0, 1\] 表示：想要学习课程 0 ，你需要先完成课程 1。  
请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。

**示例 1：**  
输入：numCourses = 2, prerequisites = \[\[1,0\]\]  
输出：true  
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

**示例 2：**  
输入：numCourses = 2, prerequisites = \[\[1,0\],\[0,1\]\]  
输出：false  
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

**提示：**  
1 <= numCourses <= 105  
0 <= prerequisites.length <= 5000  
prerequisites\[i\].length == 2  
0 <= ai, bi < numCourses  
prerequisites\[i\] 中的所有课程对互不相同

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/course-schedule

## 2.思路 ##

（1）利用 DFS 进行环检测

相关题目：  
[LeetCode\_拓扑排序\_BFS\_中等\_210.课程表 II][LeetCode_BFS_210._ II]  
[LeetCode\_贪心算法\_困难\_630.课程表 III][LeetCode_630._ III]  
[LeetCode\_拓扑排序\_BFS\_中等\_1462.课程表 IV][LeetCode_BFS_1462._ IV]

## 3.代码实现（Java） ##

//思路1————利用 DFS 进行环检测
    class Solution {
        
    
        List<Integer>[] graph;
        /*
            visited[u] = 0: 节点 u 还未被搜索
            visited[u] = 1: 节点 u 正在搜索中
            visited[u] = 2: 节点 u 已完成搜索
        */
        int[] visited;
        boolean valid = true;
    
        public boolean canFinish(int numCourses, int[][] prerequisites) {
        
            graph = buildGraph(numCourses, prerequisites);
            visited = new int[numCourses];
            for (int i = 0; i < numCourses && valid; ++i) {
        
                if (visited[i] == 0) {
        
                    dfs(i);
                }
            }
            return valid;
        }
    
        public void dfs(int u) {
        
            visited[u] = 1;
            for (int v: graph[u]) {
        
                if (visited[v] == 0) {
        
                    dfs(v);
                    if (!valid) {
        
                        return;
                    }
                } else if (visited[v] == 1) {
        
    	            //图中出现了环，更新 valid，直接返回
                    valid = false;
                    return;
                }
            }
            visited[u] = 2;
        }
    
        public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        
            List<Integer>[] graph = new ArrayList[numCourses];
            for (int i = 0; i < numCourses; i++) {
        
                graph[i] = new ArrayList<>();
            }
            for (int[] prerequisite : prerequisites) {
        
                int from = prerequisite[1];
                int to = prerequisite[0];
                graph[from].add(to);
            }
            return graph;
        }
    }

[LeetCode_BFS_210._ II]: https://blog.csdn.net/weixin_43004044/article/details/124532046
[LeetCode_630._ III]: https://blog.csdn.net/weixin_43004044/article/details/132800584
[LeetCode_BFS_1462._ IV]: https://blog.csdn.net/weixin_43004044/article/details/132824879