210. Course Schedule II - Medium

前往題目

想法

• 記得之前有寫過簡單版的，回去看了一下對於這題依舊沒有太大的頭緒，不知道該怎麼改

思路

重點是不能修所有課業的時候就是出現Cycle的時候

1. 記錄所有課的必修課
2. 對每門課進行DFS，找看看有沒有cycle，沒有的話就加到答案裡；訪問過的課程也不用再檢查一次了

Neetcode大大的解釋非常清楚，看不懂的時候可以參考

Code

class Solution {

    List<Integer> res;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] prereq = new ArrayList[numCourses];

        // Init. prereq
        for (int i = 0; i < numCourses; ++i) {
            prereq[i] = new ArrayList<Integer>();
        }

        // Add elements to prereq
        for (int[] prerequisite : prerequisites) {
            prereq[prerequisite[0]].add(prerequisite[1]);
        }

        res = new ArrayList<>();

        HashSet<Integer> visit = new HashSet<>();
        HashSet<Integer> cycle = new HashSet<>();
        
        for (int i = 0; i < numCourses; ++i) {
            if (dfs(i, visit, cycle, prereq) == false)
                return new int[0];
        }

        // After checking all the courses
        return res.stream().mapToInt(i -> i).toArray();
    }

    private boolean dfs(
        int course, 
        HashSet<Integer> visit, 
        HashSet<Integer> cycle,
        ArrayList<Integer>[] prereq
        ) {
        
        // Impossible to finish
        if (cycle.contains(course)) {
            return false;
        }
        // No need to proceed if visited already
        if (visit.contains(course)) {
            return true;
        }

        // Add the course
        cycle.add(course);

        // Check the pre of the course
        for (int pre : prereq[course]) {
            // Check validity
            if (dfs(pre, visit, cycle, prereq) == false) return false;
        }

        // After checking all pre, back to the course
        cycle.remove(course);
        visit.add(course);
        // The course is able to be taken
        res.add(course);
        return true;
    }
}

2024/04/25

• 只記得要看是否有cycle