DFS without Topological Sorting Recursive and Iterative


  • 0
    Z

    Actually we don't have to do Topological Sorting, because for this problem it just ask whether it could be Topological sorted or not. So if this graph is DAG, then it could be sorted, otherwise it couldn't. So we just to test whether there are cycles in this graph.

    // recursive
    public boolean canFinish(int n, int[][] p) {
            if (n == 0) return true;
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < n; i ++) graph.add(new ArrayList<>());
            for (int[] pair : p) graph.get(pair[0]).add(pair[1]);
            boolean[] visited = new boolean[n];
            for (int i = 0; i < n; i ++) {
                if (visited[i]) continue;
                if (!DFS(visited, new boolean[n], graph, i)) return false;
        }
            return true;
        }
        
     private boolean DFS(boolean[] visited, boolean[] inStack, List<List<Integer>> graph, int begin) {
            visited[begin] = true;
            inStack[begin] = true;
            List<Integer> list = graph.get(begin);
            for (int i : list) {
                if (!visited[i] && !DFS(visited, inStack, graph, i)) return false;
                else if (inStack[i]) return false;
            }
            inStack[begin]  = false;
            return true;
        }
    // iterative
    public boolean canFinish(int n, int[][] p) {
            if (n == 0) return true;
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < n; i ++) graph.add(new ArrayList<Integer>());
            for (int[] pair : p) graph.get(pair[0]).add(pair[1]);
            return DFS(graph);
        }
        
        private boolean DFS(List<List<Integer>> graph) {
            int n = graph.size();
            Stack<Integer> stack = new Stack<>();
            boolean[] visited = new boolean[n];
            boolean[] inStack = new boolean[n];
            
            for (int i = 0; i < n; i ++) {
                if (visited[i]) continue;
                stack.push(i);
                while (!stack.isEmpty()) {
                    int node = stack.peek();
                    visited[node] = true;
                    inStack[node] = true;
                    List<Integer> list = graph.get(node);
                    int j;
                    for (j = 0; j < list.size() && visited[list.get(j)]; j ++) 
                        if (inStack[list.get(j)]) return false;
                    if (j == list.size()) { inStack[node] = false; stack.pop();}
                    else stack.push(list.get(j));
                }
            }
            return true;
        }
    

Log in to reply
 

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