A DFS C# Solution -- 308ms

  • 0
    public bool CanFinish(int numCourses, int[,] prerequisites)
        List<int>[] depend = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++)
            depend[i] = new List<int>();
        for (int i = 0; i < prerequisites.GetLength(0); i++)
            depend[prerequisites[i, 0]].Add(prerequisites[i, 1]);
        bool[] history = new bool[numCourses];
        for (int i = 0; i < depend.Count(); i++)
            if (!dfsFinish(history, i, depend)) return false;
        return true;
    private bool dfsFinish(bool[] history, int courseNo, List<int>[] depend)
        if (history[courseNo]) return false;
        history[courseNo] = true;
        foreach (var d in depend[courseNo])
            if (!dfsFinish(history, d, depend)) return false;
        history[courseNo] = false;
        return true;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.