LeetCode 210. Course Schedule II

Course Schedule II

Topological sort.

public class Solution {
    public int[] FindOrder(int numCourses, int[,] prerequisites) {
        bool[] visited = new bool[numCourses];
        bool[] taken = new bool[numCourses];
        Stack<int> st = new Stack<int>();
        Dictionary<int, List<int>> pre = new Dictionary<int, List<int>>();
        for(int i = 0; i < numCourses; i++){
            pre[i] = new List<int>();
        }
        for(int i = 0; i < prerequisites.GetLength(0); i++){
            pre[prerequisites[i,0]].Add(prerequisites[i,1]);
        }
        bool doable = true;
        for(int i = 0; i < numCourses; i++){
            if(!visited[i] && !Check(i, visited, taken, pre, st)) doable = false;
        }
        
        if(!doable) return new int[] {};
        
        int[] ret = st.ToArray();
        Array.Reverse(ret);
        return ret;
    }
    public bool Check(int i, bool[] visited, bool[] taken, Dictionary<int, List<int>> pre, Stack<int> st){
        visited[i] = true;
        foreach (int n in pre[i]){
            if(visited[n] && !taken[n]) return false;
            if(!visited[n] && !Check(n, visited, taken, pre, st)) return false;
        }
        taken[i] = true;
        st.Push(i);
        return true;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *