simple, short, intuitive java dfs solution + union find

  • 0

    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>());
            for(int i=0;i<edges.length;i++){ //build graph
            int result = 0;
            while(visited.size()>0){ //if visited.size()>0, there are unvisited nodes
                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.