public class Solution {
    private IList<IList<int>> graph;
    private bool[] marked;
    private bool[] onStack;
    private bool hasCycle;

    public bool CanFinish(int numCourses, int[,] prerequisites) {
        graph = new List<IList<int>>();
        marked = new bool[numCourses];
        onStack = new bool[numCourses];

        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;
    }

    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;
            }
        }

        onStack[v] = false;
    }
}