[leetcode #210] Course Schedule II

Problem
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [aᵢ, bᵢ] indicates that you must take course bᵢ first if you want to take course aᵢ.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:

Input: numCourses = 2, prerequisites = [[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: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [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].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

・ 1 <= numCourses <= 2000
・ 0 <= prerequisites.length <= numCourses * (numCourses - 1)
・ prerequisites[i].length == 2
・ 0 <= aᵢ, bᵢ < numCourses
・ aᵢ != bᵢ
・ All the pairs [aᵢ, bᵢ] are distinct.

Idea
numCoursesは2000個しかないのでO(n)²)この問題は使っても通る.
Graphを利用する気がしますが、なかなか考えにくいので、まずはBrut forceで解くことにしました.
最初に与えられたnumCoursesに従ってremanifiningPrequirementsという集合リストを作成します.この資料構造は、各カリキュラムの残りの前提条件を保存します.
次に、指定された前提条件をめぐって、再生成された前提条件を格納するために必要なカリキュラムです.
受講可能な科目は選手科目があることができないので、再設定の要求に従って、選手科目がない科目だけを「可能な科目」リストに格納します.
可能な授業の空き時間にループを回って授業をすることができます.可能なカリキュラムからカリキュラムを抽出し、再生成された要件から削除します.このとき,削除した科目を受講順配列に加える.前提条件セットが空の場合は、可能なカリキュラムに科目を追加します.
カリキュラム順序のインデックスがnumCoursesと一致しない場合、すべてのカリキュラムを取得できないため、空の配列が返されます.numCoursesと一致する場合は、作成した配列を返します.
実はこうやって解くのはO(n)²)そのため、他の方法を研究したほうがいい.leetcodeにはGraphとDFSを使用するプールがあるので、再展開を参照してください.
Solution

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> remainingPrerequisites = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            remainingPrerequisites.add(new HashSet<>());
        }

        for (int[] prerequisite : prerequisites) {
            remainingPrerequisites.get(prerequisite[0]).add(prerequisite[1]);
        }

        List<Integer> possibleCourses = new ArrayList<>();
        for (int i=0; i < numCourses; i++) {
            if (remainingPrerequisites.get(i).isEmpty()) {
                possibleCourses.add(i);
            }
        }

        int[] res = new int[numCourses];
        int index = 0;
        while (!possibleCourses.isEmpty()) {
            int course = possibleCourses.remove(0);
            res[index++] = course;

            for (int i=0; i < numCourses; i++) {
                Set<Integer> set = remainingPrerequisites.get(i);
                if (set.remove(course) && set.isEmpty()) {
                    possibleCourses.add(i);
                }
            }
        }

        if (index != numCourses) {
            return new int[0];
        }

        return res;
    }
}

GraphとDFSを使用したプールは次のとおりです.

class Solution {
  static int WHITE = 1;
  static int GRAY = 2;
  static int BLACK = 3;

  boolean isPossible;
  Map<Integer, Integer> color;
  Map<Integer, List<Integer>> adjList;
  List<Integer> topologicalOrder;

  private void init(int numCourses) {
    this.isPossible = true;
    this.color = new HashMap<Integer, Integer>();
    this.adjList = new HashMap<Integer, List<Integer>>();
    this.topologicalOrder = new ArrayList<Integer>();

    // By default all vertces are WHITE
    for (int i = 0; i < numCourses; i++) {
      this.color.put(i, WHITE);
    }
  }

  private void dfs(int node) {

    // Don't recurse further if we found a cycle already
    if (!this.isPossible) {
      return;
    }

    // Start the recursion
    this.color.put(node, GRAY);

    // Traverse on neighboring vertices
    for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<Integer>())) {
      if (this.color.get(neighbor) == WHITE) {
        this.dfs(neighbor);
      } else if (this.color.get(neighbor) == GRAY) {
        // An edge to a GRAY vertex represents a cycle
        this.isPossible = false;
      }
    }

    // Recursion ends. We mark it as black
    this.color.put(node, BLACK);
    this.topologicalOrder.add(node);
  }

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

    this.init(numCourses);

    // Create the adjacency list representation of the graph
    for (int i = 0; i < prerequisites.length; i++) {
      int dest = prerequisites[i][0];
      int src = prerequisites[i][1];
      List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
      lst.add(dest);
      adjList.put(src, lst);
    }

    // If the node is unprocessed, then call dfs on it.
    for (int i = 0; i < numCourses; i++) {
      if (this.color.get(i) == WHITE) {
        this.dfs(i);
      }
    }

    int[] order;
    if (this.isPossible) {
      order = new int[numCourses];
      for (int i = 0; i < numCourses; i++) {
        order[i] = this.topologicalOrder.get(numCourses - i - 1);
      }
    } else {
      order = new int[0];
    }

    return order;
  }
}

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