[JAVA] Hashmap and array with dfs / T : O(N), S : O(N)


  • 0
    J
    class Solution {
    
        public int countComponents(int n, int[][] edges) {
            boolean[] mark = new boolean[n];
            HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
            int count = 0;
            for(int edge[] : edges){
                if(!map.containsKey(edge[0])){
                    map.put(edge[0], new HashSet<Integer>());
                }
                map.get(edge[0]).add(edge[1]);
                
                if(!map.containsKey(edge[1])){
                    map.put(edge[1], new HashSet<Integer>());
                }
                map.get(edge[1]).add(edge[0]);
            }
            
            for(int i = 0; i < n; i++){
                if(!mark[i]){
                    count++;
                    dfs(map, mark, i);
                }
            }
            
            return count;
        }
        
        public void dfs(HashMap<Integer, HashSet<Integer>> map, boolean[] mark, int i){
            if(!map.containsKey(i) || mark[i] == true)
                return;
            
            mark[i] = true;
            for(int node : map.get(i)){
                dfs(map, mark, node);
            }
        }
    }
    

Log in to reply
 

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