Simple Java solution using DFS to check if a back edge exists; Beats 95.59% of submissions


  • 0
    S

    This is a simple method to detect a cycle using dfs. This method basically checks if a back edge exists in the graph. Its a simple 2 step process.
    Step 1: construct a graph out of the prerequesite array.
    Step 2 : perform dfs. While performing dfs, keep track of the current vertex being explored in the recursion in an array say currentStack. If we encounter a vertex which is already in the currentStack, it means there is a loop in the graph.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            
            List<Integer> graph[] = new ArrayList[numCourses];
            for(int i = 0; i < numCourses; i++){
                graph[i] = new ArrayList<Integer>();
            }
            
            boolean[] visited = new boolean[numCourses];
            boolean[] currentStack = new boolean[numCourses];
            
            for(int i = 0; i < prerequisites.length; i++){
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }
            for(int i = 0; i < numCourses; i++){
                if(isCycle(graph, visited, currentStack, i)){
                    return false;
                }
            }
            return true;
        }
        
        private boolean isCycle(List<Integer> adj[], boolean[] visited, boolean[] currentStack, int start){
            
            visited[start] = true;
            currentStack[start] = true;
            Iterator<Integer> it = adj[start].iterator();
            while(it.hasNext()){
                int temp = it.next();
                if(!visited[temp] && isCycle(adj, visited, currentStack, temp)){
                    return true;
                }else if(currentStack[temp]){
                    return true;
                }
            }
            currentStack[start] = false;
            return false;
        }
    }
    

Log in to reply
 

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