AC BFS Solution with two hashmaps


  • 0
    S

    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>();
            set.add(edges[0][0]);
            set.add(edges[0][1]);
            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>();
                    list1.add(y);
                    map1.put(x,list1);
                }else{
                    map1.get(x).add(y);
                }
                
                if(!map2.containsKey(y)){
                    List<Integer> list2 = new ArrayList<Integer>();
                    list2.add(x);
                    map2.put(y,list2);
                }else{
                    map2.get(y).add(x);
                }
            }
            
            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);
                            newSet.add(num1);
                            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);
                            newSet.add(num2);
                            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();
                set.addAll(newSet);
            }
            for(int i=0; i<n; i++){
                if(!appear[i]) return false;
            }
            return map1.isEmpty() && map2.isEmpty();
        }
    }

Log in to reply
 

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