simple, short, intuitive java dfs solution + union find


  • 0
    C

    simple dfs solution

    public int countComponents(int n, int[][] edges) {
            if(n <= 1) return n;
            HashMap<Integer, List<Integer>> graph = new HashMap<>();
            HashSet<Integer> visited = new HashSet<Integer>(); //nodes in set means they are not visited
            for(int i=0;i<n;i++) { //initiate graph
                graph.put(i, new ArrayList<Integer>());
                visited.add(i);
            }
            for(int i=0;i<edges.length;i++){ //build graph
                graph.get(edges[i][0]).add(edges[i][1]);
                graph.get(edges[i][1]).add(edges[i][0]);
            }
            int result = 0;
            while(visited.size()>0){ //if visited.size()>0, there are unvisited nodes
                result++;
                dfs(graph, visited.iterator().next(), visited);
            }
            return result;
        }
        private void dfs(HashMap<Integer, List<Integer>> graph, int node, HashSet<Integer> visited){
            if(visited.contains(node)) visited.remove(node);
            else return;
            for(int i=0;i<graph.get(node).size();i++){
                dfs(graph, graph.get(node).get(i), visited);
            }
        }
    

    union-find solution

    public int countComponents(int n, int[][] edges) {
            int[] parent = new int[n];
            Arrays.fill(parent, -1);
            for(int i=0;i<edges.length;i++){
                int x = find(parent, edges[i][0]);
                int y = find(parent, edges[i][1]);
                if(x != y)
                    union(parent, x, y);
            }
            int neg1num = 0;
            for(int i=0;i<n;i++){
                if(parent[i] == -1) neg1num++;
            }
            return neg1num;
        }
    private int find(int[] parent, int v){
            while(parent[v] != -1) v = parent[v];
            return v;
        }
        private void union(int[] parent, int v1, int v2){
            int v1Set = find(parent, v1);
            int v2Set = find(parent, v2);
            parent[v1Set] = v2Set;
        }
    

Log in to reply
 

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