https://leetcode.com/problems/course-schedule/
https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java
- Topological Sorting using BFShttps://leetcode.com/problems/course-schedule/discuss/58524/Java-DFS-and-BFS-solution
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
31
32
33
34
35
36class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null) return true;
// create graph
HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
int[] incomingEdgeNum = new int[numCourses];
for (int[] edge : prerequisites) {
incomingEdgeNum[edge[0]]++;
if (!graph.containsKey(edge[1])) {
ArrayList<Integer> ls = new ArrayList<Integer>();
ls.add(edge[0]);
graph.put(edge[1], ls);
} else
graph.get(edge[1]).add(edge[0]);
}
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (incomingEdgeNum[i] == 0)
queue.offer(i);
}
int count = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
if (graph.containsKey(course)) { //need to check otherwise nullpointer error
for (int nextCourse : graph.get(course)) {
incomingEdgeNum[nextCourse]--;
count++;
if (incomingEdgeNum[nextCourse] == 0) queue.offer(nextCourse);
}
}
}
return count == prerequisites.length;
}
} - DFS
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
26class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//build graph
ArrayList[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList();
for(int[] edge:prerequisites) graph[edge[1]].add(edge[0]);
//visited flag
boolean[] visited = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!dfs(graph, visited, i)) return false;
}
return true;
}
//Directed graph cycle detection
public boolean dfs(ArrayList[] graph, boolean[] visited, int course){
if(visited[course]) return false;
visited[course]=true;
for(int i=0;i<graph[course].size();i++){
if(!dfs(graph,visited,(int)graph[course].get(i))) return false;
}
visited[course]=false;//backtracking
return true;
}
}