My accepted solution


  • 0
    S
    public class Solution {
        
        public static int labelG = 0;
        
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            
           	 labelG = numCourses;
    		  int[] topOrder = new int[numCourses];
    	      int[] visited = new int[numCourses];
    	      int[][] adjList = new int[numCourses][numCourses];
    	      int[] bound = new int[numCourses];
    	      int[] courseOrder = new int[numCourses];
    	      int[] connected = new int[numCourses];
    	       
    	      for(int[] ed: prerequisites)
    	        {
    	            int v = ed[0];
    	            int bnd = bound[v];
    	            adjList[v][bnd++] = ed[1];
    	            bound[v] = bnd;
    	            connected[ed[0]] = 1;
    	            connected[ed[1]] = 1;
    	        }
    	        
    	      for(int i = 0; i < numCourses; i++)
    	      {
    	            if(visited[i]==0 && bound[i] > 0)
    	            {
    	                DFS(i, visited, adjList, bound, topOrder,courseOrder);
    	            }
    	      }
    	      
    	      
    	      for(int[] ed:prerequisites)
    	      {
    	    	  if(topOrder[ed[0]]> topOrder[ed[1]])
    	    	  {
    	    		  return new int[0];
    	    	  }
    	      }
       
    	      int cnn = 0;
    	      for(int x = 0; x < numCourses; x++)
    	      {
    	    	  if(connected[x]==0)
    	    	  {
    	    		  courseOrder[numCourses-cnn-1] = x;
    	    		  cnn++;
    	    	  }
    	    	  
    	      }
    	      
    	      return courseOrder;
            
        }
        
        
        public void DFS(int i, int[] visited, int[][] adjList, int[] bound, int[] topOrder,int[] courseOrder)
        {
            visited[i] = 1;
            int indx = 1;
            int bnd = bound[i];
            for(int nb: adjList[i])
            {
                if(indx > bnd)
                {
                    break;    
                }
                
                if(visited[nb]==0)
                {
                    DFS(nb, visited, adjList, bound, topOrder, courseOrder);
                }
                indx++;
            }
            
            topOrder[i] = labelG;
            courseOrder[visited.length - labelG] = i;
            labelG--;
            
        }
    
    }

Log in to reply
 

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