Course Schedule I&II

DFS找环

BFS找拓扑序

Course Schedule

用DFS判断一个图是不是DAG

有向图找环

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] visited = new int[numCourses];

        // convert the edge list to adjacent list
        for(int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for(int i = 0; i < prerequisites.length; i++) {
            int parent = prerequisites[i][1];
            int child = prerequisites[i][0];
            graph[parent].add(child);
        }
        // dfs find cycle
        for(int i = 0; i < graph.length; i++) {
            if(hasCycle(i, graph, visited)) return false;
        }   

        return true;
    }

    public boolean hasCycle(int cur, ArrayList[] graph, int[] visited) {
        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;
            hasCycle = hasCycle || hasCycle(next, graph, visited); 
        }

        visited[cur] = 2;

        return hasCycle;
    }
}

Course Schedule II

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

找到一个拓扑序

BFS 找拓扑序

问题是有环的时候是没有拓扑序的

由于在 BFS 时只有 indegree = 0 时才会被加入队列，如果 graph 中有环，会出现有环的部分永远无法进入 BFS 被访问的情况，因此在结尾我们只需要看一下到底有没有点从来没被访问过即可。维护一个visitedCount

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];

        // convert edge list to adjacent lists
        for(int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        } 

        for(int[] edge : prerequisites) {
            int parent = edge[1];
            int child = edge[0];

            graph[parent].add(child);
            indegree[child]++;
        }
        // BFS
        Queue<Integer> q = new LinkedList<>();
        // indegree == 0 as a start
        for(int i = 0; i < indegree.length; i++) {
            if(indegree[i] == 0) q.offer(i);
        }

        // if all the course reached
        // 如果存在环那么有一些课时无法加入BFS
        int visitedCount = 0;
        int index = 0;

        while(!q.isEmpty()) {
            int cur = q.poll();
            visitedCount++;
            result[index++] = cur;
            for(int i = 0; i < graph[cur].size(); i++) {
                int next = (int)graph[cur].get(i);
                indegree[next]--;
                if(indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }

        return visitedCount == numCourses ? result : new int[0];
    }
}