Using DFS + Back Edge in JAVA


  • 0
    S
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int pn = prerequisites.length;
            int[][] graph = new int[numCourses][numCourses];
            
            for(int i=0; i<pn; i++)
                graph[prerequisites[i][0]][prerequisites[i][1]] = 1;
            
            return !detectCycle(graph);
        }
        
        private static boolean detectCycle(int[][] graph) {
            boolean[] visited = new boolean[graph.length];
            boolean[] recursionStack = new boolean[graph.length];
            for (int i = 0; i < graph.length; i++) {
                if (!visited[i])
                    if (detectCycle(graph, i, visited, recursionStack)) {
                        System.out.println(i);
                        return true;
                    }
            }
            return false;
        }
    
        private static boolean detectCycle(int[][] graph, int source, boolean[] visited, boolean[] recursionStack) {
            int n = graph.length;
            visited[source] = true;
            recursionStack[source] = true;
    
            for (int i = 0; i < n; i++) {
                if (graph[source][i] == 1) {
                    if (!visited[i]) {
                        if (detectCycle(graph, i, visited, recursionStack))
                            return true;
                    } else if (recursionStack[i])
                        return true;
                }
            }
            recursionStack[source] = false;
            return false;
        }
    }
    
    

Log in to reply
 

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