AC solution in Java


  • 0
    L
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            if (numCourses <= 1) return true;
            List<List<Integer>> adjs = new ArrayList<>();
            boolean[] visited = new boolean[numCourses];
            while (numCourses-- > 0) adjs.add(new ArrayList<>());
            for (int[] edge : prerequisites) adjs.get(edge[0]).add(edge[1]);
            return !hasCycle(adjs, visited);
        }
        
        private boolean hasCycle(List<List<Integer>> adjs, boolean[] visited) {
            boolean[] onStack = new boolean[visited.length];
            for (int i = 0; i < visited.length; i++) {
                if (visited[i] == false) {
                    if (dfs(i, adjs, visited, onStack) == true) return true;
                }
            }
            return false;
        }
        
        private boolean dfs(int node, List<List<Integer>> adjs, boolean[] visited, boolean[] onStack) {
            visited[node] = true; onStack[node] = true;
            for (int to : adjs.get(node)) {
                if (visited[to] == false) {
                    if (dfs(to, adjs, visited, onStack) == true) return true;
                } else if (onStack[to] == true) {
                    return true;
                }
            }
            onStack[node] = false;
            return false;
        }
    }
    

    This question immediately reads as a question to detect cycles in a directed graph

    1. convert it to directed graph
    2. detect directed cycles

    Another way is to use incoming and outgoing edges. More on this in a post I wrote for the follow-up question.

    More on onStack array:

    onStack is set to true when we first visit it and it is set to false after we have explored all the outgoing edges.

    The way to think about how it detects directed cycles proceeds like this. If a directed graph has a cycle, it must mean that one of the nodes in the cycle must have an outgoing path that leads back to itself. The for loop in dfs method explores all outgoing paths from a node. This node is on a cycle if a successive dfs call finds a path back to the current node.

    On the other hand, if all edges are explored and no returning paths are found, this node is not on a cycle. Hence, we only set onStack to be false after the for loop.


  • 0
    G

    Hi ,

    It would be great if you can explain the logic . Like what is the significance of Onstack. It is getting reset- ed after every dfs loop. Sorry i tried to understand but i am getting confused.

    Thanks,
    Guru


  • 0
    L

    Hi there,

    Sorry for the confusion. I have edited my post which is waiting to be approved. I hope it would clarify some of your doubts.

    :)
    Lan


Log in to reply
 

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