拓扑排序。Time = O(V+E), Space = O(V+E)，V为点数，E为边数，拓扑排序仅遍历所有的点和边一次。
算法：
1) 统计每一个点的 indegree
2) 进行拓扑排序：
首先，把 indegree = 0 的所有点拿到
然后，将这些 indegree = 0 的点放入 queue，开始进行 bfs
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites.length == 0) {
return true;
}
int[] indegree = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < prerequisites.length; i++) {
indegree[prerequisites[i][0]]++;
map.put(prerequisites[i][1], map.getOrDefault(prerequisites[i][1], new ArrayList<>()));
map.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int curCourse = queue.poll();
List<Integer> subCourses = map.get(curCourse);
if (subCourses != null) {
for (int subCourse : subCourses) {
if (--indegree[subCourse] == 0) {
queue.offer(subCourse);
}
}
}
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] != 0) {
return false;
}
}
return true;
}
}
Detect if there is cycle in a graph.
Time = O(V+E), Space = O(V+E)
class Solution {
enum Status {
NOT_VISITED, VISITED, VISITING;
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < prerequisites.length; i++) {
map.put(prerequisites[i][1], map.getOrDefault(prerequisites[i][1], new ArrayList<>()));
map.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
// 0 -> not visited, 1 -> visited, 2 -> visiting
Status[] visited = new Status[numCourses];
for (int i = 0; i < numCourses; i++) {
// if there is a cycle, return false
if (hasCycle(i, map, visited)) {
return false;
}
}
return true;
}
private boolean hasCycle(int curCourse, Map<Integer, List<Integer>> map, Status[] visited) {
if (visited[curCourse] == Status.VISITING) {
return true;
}
if (visited[curCourse] == Status.VISITED) {
return false;
}
visited[curCourse] = Status.VISITING;
if (map.get(curCourse) != null) {
for (int nextCourse : map.get(curCourse)) {
if (dfsHelper(nextCourse, map, visited)) {
return true;
}
}
}
visited[curCourse] = Status.VISITED;
return false;
}
}