Update Number of Connected Components in an Undirected Graph.java

varunu28 · web-flow · commit e085714d8caa · 2022-12-08T09:32:42.000-08:00
diff --git a/Medium/Number of Connected Components in an Undirected Graph.java b/Medium/Number of Connected Components in an Undirected Graph.java
@@ -1,51 +1,29 @@
 class Solution {
-  public int countComponents(int n, int[][] edges) {
-    DisjointSet disjointSet = new DisjointSet(n);
-    for (int[] edge : edges) {
-      disjointSet.union(edge[0], edge[1]);
-    }
-    Set<Integer> rootSet = new HashSet<>();
-    for (int i = 0; i < n; i++) {
-      rootSet.add(disjointSet.find(i));
-    }
-    return rootSet.size();
-  }
-
-  private static class DisjointSet {
-
-    private final int[] root;
-    private final int[] rank;
-
-    public DisjointSet(int size) {
-      this.root = new int[size];
-      this.rank = new int[size];
-      for (int i = 0; i < size; i++) {
-        this.root[i] = i;
-        this.rank[i] = 1;
-      }
-    }
-
-    public void union(int nodeOne, int nodeTwo) {
-      int rootOne = find(nodeOne);
-      int rootTwo = find(nodeTwo);
-      if (rootOne != rootTwo) {
-        if (this.rank[rootOne] > this.rank[rootTwo]) {
-          this.root[rootTwo] = rootOne;
-        } else if (this.rank[rootOne] < this.rank[rootTwo]) {
-          this.root[rootOne] = rootTwo;
-        } else {
-          this.root[rootTwo] = rootOne;
-          this.rank[rootOne]++;
+    public int countComponents(int n, int[][] edges) {
+        Map<Integer, Set<Integer>> graph = new HashMap<>();
+        for (int[] edge : edges) {
+            graph.computeIfAbsent(edge[0], k -> new HashSet<>()).add(edge[1]);
+            graph.computeIfAbsent(edge[1], k -> new HashSet<>()).add(edge[0]);
         }
-      }
-    }
-
-
-    public int find(int node) {
-      if (node == root[node]) {
-        return node;
-      }
-      return root[node] = find(root[node]);
+        int connectedComponentCount = 0;
+        Set<Integer> visited = new HashSet<>();
+        for (int i = 0; i < n; i++) {
+            if (!visited.contains(i)) {
+                Queue<Integer> queue = new LinkedList<>();
+                visited.add(i);
+                queue.add(i);
+                while (!queue.isEmpty()) {
+                    int removed = queue.remove();
+                    for (Integer neighbor : graph.getOrDefault(removed, new HashSet<>())) {
+                        if (!visited.contains(neighbor)) {
+                            queue.add(neighbor);
+                            visited.add(neighbor);
+                        }
+                    }
+                }
+                connectedComponentCount++;
+            }
+        }
+        return connectedComponentCount;
     }
-  }
 }
