C# Solution


  • 0

    DFS

            public bool CanFinish(int numCourses, int[,] prerequisites)
            {
                if (prerequisites.GetLength(0) == 0)
                    return true;
    
                bool[] visited = new bool[numCourses];
                List<int>[] graph = new List<int>[numCourses];
    
                for (int i = 0; i <= numCourses - 1; i++)
                    graph[i] = new List<int>();
    
                for (int i = 0; i <= prerequisites.GetLength(0) - 1; i++)
                    graph[prerequisites[i, 0]].Add(prerequisites[i, 1]);
    
                for (int i = 0; i <= graph.Length - 1; i++)
                    if (!visited[i])
                        if (!DFS(graph, visited, new bool[numCourses], i))
                            return false;
    
                return true;
            }
    
            private bool DFS(List<int>[] graph, bool[] visited, bool[] currentPath, int course)
            {
                if (currentPath[course])
                    return false;
    
                visited[course] = true;
                currentPath[course] = true;
                
                for (int i = 0; i < graph[course].Count; i++)
                    if (!DFS(graph, visited, currentPath, graph[course][i]))
                            return false;
                
                currentPath[course] = false;
    
                return true;
            }

Log in to reply
 

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