Java 2 solutions, union-find & dfs


  • 0
    M

    Union Find Method:

        public int countComponents_unionFind(int n, int[][] edges) {
            int[] uf = new int[n];
            for(int i=0; i<n; i++)
                uf[i] = i;
            for(int[] edge : edges){
                union(edge[0], edge[1], uf);
            }
            Set<Integer> set = new HashSet<>();
            for(int i=0; i<n; i++){
            	set.add(find(i, uf));
            }
            return set.size();
        }
        private void union(int node1, int node2, int[] uf){
            uf[find(node1, uf)] = find(node2, uf);
        }
        private int find(int node, int[] uf){
            if(uf[node] == node) return node;
            uf[node] = find(uf[node], uf);
            return uf[node];
        }
    

    DFS Method:

        public int countComponents_dfs(int n, int[][] edges) {
            List<Integer>[] adj = new LinkedList[n];
            for(int i=0; i<n; i++)
                adj[i] = new LinkedList<Integer>();
            for(int[] edge : edges){
                adj[edge[0]].add(edge[1]);
                adj[edge[1]].add(edge[0]);
            }
            Set<Integer> set = new HashSet<>();
            int count = 0;
            for(int i=0; i<n; i++){
                if(set.add(i)){
                    count++;
                    dfs(i, adj, set);
                }
            }
            return count;
        }
        private void dfs(int root, List<Integer>[] adj, Set<Integer> set){
            for(int neighbor : adj[root]){
                if(set.add(neighbor))
                    dfs(neighbor, adj, set);
            }
        }
    

Log in to reply
 

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