210.Course-Schedule-II

210. Course Schedule II

题目地址

https://leetcode.com/problems/course-schedule-ii/

题目描述

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:
Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished  course 0. So the correct course order is [0,1] .

Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both  courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

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

代码

Approach 1: DFS

DFS 需要 visited 数组来标记三种状态：

• 0 => 未访问过

• 1 => 正在访问

• 2 => 已访问，并通过

class Solution {
  public int[] findOrder(int numCourses, int[][] prerequisites) {

    Map<Integer, List<Integer>> adjs = new HashMap();
    for (int[] pair : prerequisites) {
      adjs.putIfAbsent(pair[1], new ArrayList());
      adjs.get(pair[1]).add(pair[0]);
    }

    int[] visited = new int[numCourses];
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
      if (!topoSort(res, adjs, visited, i)) {
        return new int[0];
      }
    }

    int[] result = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
      result[i] = res.get(i);
    }
    return result;
  }

  private boolean topoSort(List<Integer> res, Map<Integer, List<Integer>> adjs, int[] visited, int i) {

    if (visited[i] == 2) {
      return true;    // 排序成功
    } else if (visited[i] == 1) {
      return false; // 正在排序
    }

    visited[i] = 1; // 正在排序
    for (int j : adjs.getOrDefault(i, new ArrayList<Integer>())) {
      if (topoSort(res, adjs, visited, j) == false) {
        return false;
      }
    }
    visited[i] = 2; // 排序成功
    res.add(0, i);

    return true;
  }

}

Approach #2 BFS

BFS 需要 degree 数组来标记层数

• 每出现一次 degree++

• degree 越高优先级越低

BFS 遍历从dgree == 0 的元素开始

• 遍历每个元素的下一层元素，将其下层元素的 degree--

• 如果下层元素存在 degree == 0, 加入到 results 数组中

• 否则，从 queue 中重新吐出元素，进行遍历

最后需要比较结果 results 的长度和 n 是否相同，相同才有解

class Solution {
  public int[] findOrder(int numCourses, int[][] prerequisites) {

    int[] degree = new int[numCourses];
    Map<Integer, List<Integer>> adjs = new HashMap<>();
    for (int[] edge : prerequisites) {
      degree[edge[0]]++;
      adjs.putIfAbsent(edge[1], new ArrayList<Integer>());
      adjs.get(edge[1]).add(edge[0]);
    }

    return BFS(degree, adjs);
  }

  private int[] BFS(int[] degree, Map<Integer, List<Integer>> adjs) {
    int[] ans = new int[degree.length];
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < degree.length; i++) {
      if (degree[i] == 0) queue.offer(i);
    }

    int visited = 0;
    while (!queue.isEmpty()) {
      int from = queue.poll();
      ans[visited++] = from;
      for (int to: adjs.getOrDefault(from, new ArrayList<Integer>())) {
        degree[to]--;
        if (degree[to] == 0) {
          queue.offer(to);
        }
      }
    }

    return visited == degree.length ? ans : new int[0];
  }
}