你这个学期必须选修 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]
中的所有课程对 互不相同
思路:构建邻接表,然后用dfs遍历,判断是否有环,注意构建邻接表时的顺序,是谁到谁,这里根据题目是反着来的
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
boolean[] onPath;
boolean[] visited;
boolean hasCycle = false;
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] list = buildGraph(numCourses, prerequisites);
onPath = new boolean[numCourses];
visited = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
traverse(list, i);
}
return !hasCycle;
}
void traverse(List<Integer>[] graph, int s) {
if (onPath[s]) {
hasCycle = true;
}
if (hasCycle || visited[s]) {
return;
}
onPath[s] = true;
visited[s] = true;
for (int t : graph[s]) {
traverse(graph, t);
}
onPath[s] = false;
}
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new LinkedList[numCourses];
// Arrays.fill(graph, new LinkedList<Integer>());
for (int i = 0; i < numCourses; i++) {
graph[i] = new LinkedList<>();
}
for (int[] prereq : prerequisites) {
int start = prereq[1];
int end = prereq[0];
graph[start].add(end);
}
return graph;
}
}
//leetcode submit region end(Prohibit modification and deletion)