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

course-schedule-ii.cs

public class Solution {
    private IList<IList<int>> graph;
    private bool[] marked;
    private bool[] onStack;
    private bool hasCycle;
    private Stack<int> s;
    
    public int[] FindOrder(int numCourses, int[,] prerequisites) {
        graph = new List<IList<int>>();
        marked = new bool[numCourses];
        onStack = new bool[numCourses];
        s = new Stack<int>();
        
        for (int i = 0; i < numCourses; i++) {
            graph.Add(new List<int>());
        }
        
        int numEdges = prerequisites.Length >> 1;
        for (int i = 0; i < numEdges; i++) {
            graph[prerequisites[i, 1]].Add(prerequisites[i, 0]);
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle) break;
            if (!marked[i]) dfs(i);
        }   
        
        return hasCycle ? new int[0] : s.ToArray();
    }
    
    private void dfs(int v) {
        marked[v] = true;
        onStack[v] = true;
         
        foreach (int w in graph[v]) {
            if (!marked[w]) dfs(w);
            else if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }
        
        s.Push(v);
        onStack[v] = false;
    }
}