Share my accepted java solution


  • 0
    M

    used BFS and DFS. DFS had a better performance than BFS in my solution.

       public int countComponents(int n, int[][] edges) {
        //build a graph
        HashMap<Integer, List<Integer>> graph = new HashMap<>();
        for(int i=0;i<edges.length;i++){
            List<Integer> vertex = null;
            if(graph.containsKey(edges[i][0])){
                vertex = graph.get(edges[i][0]);
            }else{
                vertex = new ArrayList<>();    
            }
            vertex.add(edges[i][1]);
            graph.put(edges[i][0], vertex);
        }
        for(int i=0;i<edges.length;i++){
            List<Integer> vertex = null;
            if(graph.containsKey(edges[i][1])){
                vertex = graph.get(edges[i][1]);
            }else{
                vertex = new ArrayList<>();    
            }
            vertex.add(edges[i][0]);
            graph.put(edges[i][1], vertex);
        }        
        HashMap<Integer, Boolean> visited = new HashMap<>();
        for(int i=0;i<n;i++){
            visited.put(i,false);
        }
        
        int tot = 0;
        for(int i=0;i<n;i++){
            if(visited.get(i)) continue;
            tot++;
            bfs(i , graph, visited);  // or dfs(i,graph,visited);
        }
        return tot;
    }
    private void bfs(int curr,HashMap<Integer,List<Integer>> graph, HashMap<Integer, Boolean> visited){
    	if(visited.get(curr)) return;
    	Queue<Integer> que = new LinkedList<>();
    	que.add(curr);
    	while(!que.isEmpty()){
    		int temp = que.poll();
    		for(Integer I : graph.get(temp)){
    			if(visited.get(I)) continue;
    			visited.put(I, true);
    			que.add(I);
    		}
    	}
    	return;
    }
    private void dfs(int curr, HashMap<Integer,List<Integer>> graph, HashMap<Integer, Boolean> visited){
        // if it is a visited, return
        if(visited.get(curr)){
            return ;
        }
        //check if it is visited
        visited.put(curr,true);
        List<Integer> vertex = graph.get(curr);
        if(vertex==null) return ;
        
        for(int i=0;i<vertex.size();i++){
            dfs(vertex.get(i), graph, visited);
        }
        return ;
    }

Log in to reply
 

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