这题的本质就是,给你一个代表 graph 的 adjacency array,判断 graph 是否有环。其实和 Graph Valid Tree 非常像。
DFS 找环性能优异,击败了 98.42 % 的提交~
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
int[] visited = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList<Integer>();
}
for(int[] num : prerequisites){
int parent = num[1];
int child = num[0];
graph[parent].add(child);
}
for(int i = 0; i < numCourses; i++){
if(visited[i] == 0 && hasCycle(i, visited, graph)) return false;
}
return true;
}
private boolean hasCycle(int cur, int[] visited, ArrayList[] graph){
visited[cur] = 1;
boolean hasCycle = false;
for(int i = 0; i < graph[cur].size(); i++){
int next = (int) graph[cur].get(i);
if(visited[next] == 1) return true;
else if(visited[next] == 0){
hasCycle = hasCycle || hasCycle(next, visited, graph);
}
}
visited[cur] = 2;
return hasCycle;
}
}
思路上承接了原来的 topological sort BFS 解法,建 array 保存所有节点的 indegree,同时有数据结构存储每个节点的 children.
由于在 BFS 时只有 indegree = 0 时才会被加入队列,如果 graph 中有环,会出现有环的部分永远无法进入 BFS 被访问的情况,因此在结尾我们只需要看一下到底有没有点从来没被访问过即可。
这种情况的问题和当初面试时候问为什么 Java GC 里不只依靠 refernce counting 做的问题是一样的,就是当某个局部出现环形时,无法通过 BFS 建 reference count 的方式使所有点的当前 count = 0,因为所有点的 indegree 都非 0,无从开始。
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
int[] indegree = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList<Integer>();
}
for(int[] num : prerequisites){
int parent = num[1];
int child = num[0];
graph[parent].add(child);
indegree[child] ++;
}
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) queue.offer(i);
}
int visitedCount = 0;
while(!queue.isEmpty()){
int cur = queue.poll();
visitedCount ++;
for(int i = 0; i < graph[cur].size(); i++){
int next = (int) graph[cur].get(i);
indegree[next] --;
if(indegree[next] == 0){
queue.offer(next);
}
}
}
return (visitedCount == numCourses);
}
}
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] rst = new int[numCourses];
int[] indegree = new int[numCourses];
ArrayList[] graph = new ArrayList[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList();
}
for(int[] edge : prerequisites){
int parent = edge[1];
int child = edge[0];
graph[parent].add(child);
indegree[child] ++;
}
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) queue.offer(i);
}
int index = 0;
int visitedCount = 0;
while(!queue.isEmpty()){
int cur = queue.poll();
rst[index ++] = cur;
visitedCount ++;
for(int i = 0; i < graph[cur].size(); i++){
int next = (int) graph[cur].get(i);
indegree[next] --;
if(indegree[next] == 0){
queue.offer(next);
}
}
}
return (visitedCount == numCourses) ? rst : new int[0];
}
}