# My O(V+E)? BFS Java Solution

• 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>());
}
for(int inV=0;inV<numCourses;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);