My O(V+E)? BFS Java Solution


  • 0
    W

    Instead of adjacent matrix, I basically use 2 maps as Map<Integer, Set<Integer>> to check the in and out. The code is as below. I think the time complexity should be O(V+E), but not sure though.

    public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[][] edges=prerequisites;
            if(numCourses==0 || edges.length==0) return true;
            Map<Integer, Set<Integer>> mapIn=new HashMap<Integer, Set<Integer>>();
            Map<Integer, Set<Integer>> mapOut=new HashMap<Integer, Set<Integer>>();
            for(int[] edge : edges){
                int pre=edge[1];
                int current=edge[0];
                if(!mapIn.containsKey(current)) mapIn.put(current, new HashSet<Integer>());
                if(!mapOut.containsKey(pre)) mapOut.put(pre, new HashSet<Integer>());
                mapIn.get(current).add(pre);
                mapOut.get(pre).add(current);
            }
            Queue<Integer> queue=new LinkedList<Integer>();
            for(int inV=0;inV<numCourses;inV++)
                if(!mapIn.containsKey(inV)) queue.add(inV);
            while(!queue.isEmpty()){
                int vertix=queue.poll();
                if(!mapOut.containsKey(vertix)) continue;
                for(int next : mapOut.get(vertix)){
                    if(!mapIn.containsKey(next)) continue;
                    mapIn.get(next).remove(vertix);
                    if(mapIn.get(next).size()==0){
                        mapIn.remove(next);
                        queue.add(next);
                    }
                }
                if(mapIn.containsKey(vertix)) mapIn.remove(vertix);
                mapOut.remove(vertix);
            }
            return mapIn.isEmpty() && mapOut.isEmpty();
        }

Log in to reply
 

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