A DFS C# Solution -- 308ms


  • 0
    L
    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.