My accepted solution


  • 0
    S
    public class Solution {
        
        public static int labelG = 0;
        
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            
            
            int[][] matrix = new int[numCourses][numCourses];
    	    int[] index = new int[numCourses];
    		labelG = numCourses;
    		int[] visited = new int[numCourses];
    		int[] toporder = new int[numCourses]; 
    		
    		for(int[] edge: prerequisites)
    		{
    			int v = edge[0];
    			int ind = index[v];
    			matrix[v][ind++] = edge[1];
    			index[v] = ind;
    		}
    		
    		for(int i = 0; i < numCourses; i++)
    		{
    			if(visited[i]==0 && index[i]>0)
    			{
    				DFS(matrix, i, visited, toporder, labelG, index);
    			}
    		}
    		
    		
    		for(int[] edge: prerequisites)
    		{
    			if(toporder[edge[0]] >= toporder[edge[1]])
    			{
    				return false;
    			}
    		}
    		
    		return true;
    
            
        }
        
        
        public static void DFS(int[][] matrix, int i, int[] visited, int[] toporder, int label, int[] index)
    	{
    		visited[i] = 1;
    		int[] edges = matrix[i];
    		int bound = index[i];
    		for(int j=1; j <= bound;j++)
    		{
    			int e = edges[j-1];
    			if(visited[e]==0)
    			{
    				DFS(matrix, e, visited,toporder, labelG, index);
    			}
    		}
    		
    		toporder[i] = labelG;
    		labelG--;
    		
    	}
    }

Log in to reply
 

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