There are a total of n courses you have to take, labeled from 0 to n-1.

    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

    Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

    Example 1:

    1. Input: 2, [[1,0]] 
    2. Output: true
    3. Explanation: There are a total of 2 courses to take. 
    4.              To take course 1 you should have finished course 0. So it is possible.

    Example 2:

    1. Input: 2, [[1,0],[0,1]]
    2. Output: false
    3. Explanation: There are a total of 2 courses to take. 
    4.              To take course 1 you should have finished course 0, and to take course 0 you should
    5.              also have finished course 1. So it is impossible.

    Note:

    1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
    2. You may assume that there are no duplicate edges in the input prerequisites.

    题意

    假设选课时有一些课程有前置课程要求，给定一系列课程及其所有的前置课程，判断能否上完所有课。

    思路

    很典型的拓扑排序问题，经典解法有 BFS 和 DFS 两种。当图中存在环时则没有办法上完所有课。

    代码实现 - BFS

    1. class Solution {
    2.     public boolean canFinish(int numCourses, int[][] prerequisites) {
    3.         int[] inDegree = new int[numCourses];                // 入度数组
    4.         List<List<Integer>> edge = new ArrayList<>();        // 记录图信息
    5.         // 初始化邻接表
    6.         for (int i = 0; i < numCourses; i++) {
    7.             edge.add(new ArrayList<>());
    8.         }
    9.         // 生成图并记录初始入度信息
    10.         for (int i = 0; i < prerequisites.length; i++) {
    11.             inDegree[prerequisites[i][0]]++;
    12.             edge.get(prerequisites[i][1]).add(prerequisites[i][0]);
    13.         }
    14.         // 将所有入度为0的结点入队
    15.         Queue<Integer> q = new ArrayDeque<>();
    16.         for (int i = 0; i < numCourses; i++) {
    17.             if (inDegree[i] == 0) {
    18.                 q.offer(i);
    19.             }
    20.         }
    21.         // 更新结点入度和队列，并记录拓扑序列中结点的个数
    22.         int count = 0;
    23.         while (!q.isEmpty()) {
    24.             int u = q.poll();
    25.             count++;
    26.             for (int i = 0; i < edge.get(u).size(); i++) {
    27.                 int v = (int) edge.get(u).get(i);
    28.                 inDegree[v]--;
    29.                 if (inDegree[v] == 0) {
    30.                     q.offer(v);
    31.                 }
    32.             }
    33.         }
    34.         // 如果有结点不在拓扑序列中，说明图存在环
    35.         return count == numCourses;
    36.     }
    37. }

    代码实现 - DFS

    1. // DFS方法实际上就是判断是否为有向无环图
    2. class Solution {
    3.     private boolean[] visit;                // 记录结点是否被访问
    4.     private boolean[] inStack;                // 记录结点是否还在递归栈中
    5.     private List<List<Integer>> edge;        // 记录图
    7.     public boolean canFinish(int numCourses, int[][] prerequisites) {
    8.         visit = new boolean[numCourses];
    9.         inStack = new boolean[numCourses];
    10.         edge = new ArrayList<>();
    11.         // 初始化邻接表
    12.         for (int i = 0; i < numCourses; i++) {
    13.             edge.add(new ArrayList<>());
    14.         }
    15.         // 生成图
    16.         for (int i = 0; i < prerequisites.length; i++) {
    17.             edge.get(prerequisites[i][1]).add(prerequisites[i][0]);
    18.         }
    19.         // DFS处理
    20.         for (int i = 0; i < numCourses; i++) {
    21.             if (!visit[i]) {
    22.                 boolean flag = dfs(i);
    23.                 if (!flag) return false;        // 存在环则不可能有拓扑序列
    24.             }
    25.         }
    26.         return true;
    27.     }
    29.     private boolean dfs(int u) {
    30.         visit[u] = true;
    31.         inStack[u] = true;
    32.         for (int v : edge.get(u)) {
    33.             if (!visit[v]) {
    34.                 boolean flag = dfs(v);
    35.                 if (!flag) return false;
    36.             } else if (inStack[v]) {
    37.                 return false;        // 如果下一条边连接的结点还在递归栈中，说明存在环
    38.             }
    39.         }
    40.         inStack[u] = false;            // 所有出边处理完后，将当前结点排除在递归栈外
    41.         return true;
    42.     }
    43. }