# AC BFS Solution with two hashmaps

• My BFS solution with two hashmaps.

``````    public boolean validTree(int n, int[][] edges) {
int m = edges.length;
if(m==0) return n==1;
if(m*2 < n) return false;

Map<Integer, List<Integer>> map1 = new HashMap<Integer, List<Integer>>();
Map<Integer, List<Integer>> map2 = new HashMap<Integer, List<Integer>>();
boolean[] appear = new boolean[n];

Set<Integer> set = new HashSet<Integer>();
appear[edges[0][0]] = true;
appear[edges[0][1]] = true;

for(int i=1; i<m; i++){
int[] edge = edges[i];
int x = edge[0];
int y = edge[1];

if(!map1.containsKey(x)){
List<Integer> list1 = new ArrayList<Integer>();
map1.put(x,list1);
}else{
}

if(!map2.containsKey(y)){
List<Integer> list2 = new ArrayList<Integer>();
map2.put(y,list2);
}else{
}
}

while(!set.isEmpty()){
HashSet<Integer> newSet = new HashSet<Integer>();
for(int key: set){
if(map1.containsKey(key)){
List<Integer> list = map1.get(key);

while(!list.isEmpty()){
int num1 = list.get(0);
if(set.contains(num1) || newSet.contains(num1)) return false;
list.remove(0);
appear[num1] = true;
if(map2.containsKey(num1)){
map2.get(num1).remove(Integer.valueOf(key));
if(map2.get(num1).isEmpty()){
map2.remove(num1);
}
}
}
map1.remove(Integer.valueOf(key));
}
else if(map2.containsKey(key)){
List<Integer> list = map2.get(key);
while(!list.isEmpty()){
int num2 = list.get(0);
if(set.contains(num2) || newSet.contains(num2)) return false;
list.remove(0);
appear[num2] = true;
if(map1.containsKey(num2)){
map1.get(num2).remove(Integer.valueOf(key));
if(map1.get(num2).isEmpty()){
map1.remove(num2);
}
}
}
map2.remove(Integer.valueOf(key));
}
}
set.clear();