O(E) Solution - DFS based


  • 9
    R

    I couldn't really see anyone posting an O(E) solution. Here's one in Java. It is a dfs solution that tries to find a cycle. The code doesn't even use the first parameter numCources. The graph is stored in a map, which allows to completely ignore courses that no other courses depend on. While navigating the graph (using dfs) the dependencies get removed one by one until the graph is empty or a cycle was found.

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] p : prerequisites) {
            if (!map.containsKey(p[0])) {
                map.put(p[0], new HashSet<>());
            }
            map.get(p[0]).add(p[1]);
        }
        while (!map.isEmpty()) {
            if(dfs(map.keySet().iterator().next(), map, new HashSet<>())) return false;
        }
        return true;
    }
    private boolean dfs(int start, Map<Integer,Set<Integer>> map, Set<Integer> visited) {
        if (visited.contains(start)) return true;
        if (!map.containsKey(start)) return false;
        visited.add(start);
        while (!map.get(start).isEmpty()) {
            int n = map.get(start).iterator().next();
            if (dfs(n, map, visited)) return true;
            map.get(start).remove(n);
        }
        map.remove(start);
        visited.remove(start);
        return false;
    }

  • 0
    B

    @ruben3 you are calling map.remove in a while-loop. I doubt that is an O(E) algorithm.


  • 0
    R

    @baihuajun24 It doesn't really matter that map.remove() is called in the while loop, because it takes constant time to remove from the HashMap. There is some discussion about it here: http://stackoverflow.com/questions/4577998/time-complexity-of-hashmap-methods.


  • 0
    Z

    I had a similar idea like yours. But My code is exceeding time limit. Can you please help me to optimize this code? Also, I am having trouble with calculating the order of my code. Is my order O(E) as well, since I am doing DFS?

    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            if(prerequisites == null || prerequisites.length ==0) return true;
            Map<Integer, List<Integer>> preByCourse = new HashMap<>();
            for(int[] pre : prerequisites){
                int course = pre[0];
                int req = pre[1];
                if(!preByCourse.containsKey(course)){
                    preByCourse.put(course, new ArrayList<>());
                }
                preByCourse.get(course).add(req);
                
            }
            
            Set<Integer> visited = new HashSet<>();
            for(Integer course : preByCourse.keySet()){
                boolean possible = visit(course, visited, new HashSet<>(), preByCourse);
                if(!possible){
                    return false;
                }
            }
            
            return true; 
            
        }
        
        public boolean visit(Integer course, Set<Integer> visited, Set<Integer> localVisited, Map<Integer, List<Integer>> preByCourse){
            if(visited.contains(course)){
                return true;
            }
            
            if(localVisited.contains(course)){
                return false;
            }
            
            Set<Integer> lVisited =new HashSet<>(localVisited);
            lVisited.add(course);
            
             if(!preByCourse.containsKey(course)){
                 visited.add(course);
                 return true;
             }
            boolean possible = true;
            for(Integer prereq : preByCourse.get(course)){
                possible &= visit(prereq, visited, lVisited, preByCourse);
            }
            
            visited.add(course);
            return possible;
        }
    }
    

Log in to reply
 

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