C# DFS Topological Sort Solution (Beats 95%)


  • 0
    K
    public class Solution {
        public int[] FindOrder(int numCourses, int[,] prerequisites) {
            List<int>[] arr = new List<int>[numCourses];
            bool[] visited = new bool[numCourses];
            bool[] tmpVisited = new bool[numCourses];
            Stack<int> stack = new Stack<int>();
            
            for(int i = 0; i < numCourses; ++i){
                arr[i] = new List<int>();
            }
            
            for(int i = 0; i < prerequisites.GetLength(0); ++i){
                arr[prerequisites[i,1]].Add(prerequisites[i,0]);
            }
            
            for(int i = 0; i < numCourses; ++i){
                if(!Visit(arr, visited, tmpVisited, stack, i))
                    return new int[0];
            }
            
            int[] result = new int[numCourses];
            int j = 0;
            while(stack.Count != 0){
                result[j++] = stack.Pop();
            }
            return result;
        }
        
        private bool Visit(List<int>[] graph, bool[] visited, bool[] tmpVisited, Stack<int> stack, int node){
            if(tmpVisited[node])
                return false;
            if(visited[node])
                return true;
            
            tmpVisited[node] = true;
            
            foreach(int n in graph[node]){
                if(!Visit(graph, visited, tmpVisited, stack, n))
                    return false;
            }
            
            tmpVisited[node] = false;
            visited[node] = true;
            stack.Push(node);
            return true;
        }
    }
    

Log in to reply
 

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