Count Connected Components - JS Solution

JS
Editorial

Approach

  • We are given a graph with n nodes labeled from 0 to n − 1 and an edges list, where each edge is a pair [u, v] indicating an undirected connection between node u and node v. The goal is to determine how many connected components (disconnected groups of nodes) this graph has.
  • Intuition:
    At the very beginning, when we have no edges, each node stands alone as its own connected piece of the graph. So we conceptually start with n separate components.

    As we process edges one by one:
    • If an edge [u, v] connects two nodes that were in different components before encountering this edge, then it merges the component containing node u and the component containing node v into a single larger component, and the total number of components decreases by 1.
    • If an edge [u, v] connects two nodes that were already connected (i.e., already in the same component before encountering this edge), then it does not merge two components into one and therefore does not reduce the component count — it simply adds another connection inside that same component.
    Once we have processed all edges this way, whichever number of components remains is exactly the number of disconnected groups in the graph.

    The key difficulty is efficiently answering the question: "Are these two nodes already in the same connected component, or not?" This is precisely what the Disjoint-Set / Union–Find structure is good at.
  • Disjoint-Set (Union–Find) Structure:
    We maintain two arrays:
    • parent[i] — stores the parent of node i in the disjoint-set forest. Initially, parent[i] = i for every node i, meaning each node starts as its own separate set (component).
    • rank[i] — used as a union-by-rank heuristic. For a root node i, rank[i] is an upper bound on the number of parent[] links one might follow to reach node i from any node in its set. Since each node initially forms a single-node set (already pointing to itself as its own root), its maximum possible parent-link depth is 0, so all rank[i] values are initialized to 0. It is meaningful only for root nodes; for non-root nodes, it may be outdated and is not used to guide unions.

    Why use rank and path compression? Rank makes sure trees grow minimally by always attaching the shallower tree under the deeper one, while path compression flattens existing paths during find() calls by making nodes point directly to their root. Used together, they keep the forest almost flat at all times, ensuring each find() operation runs in amortized near-constant time for all practical n.
  • Find(x) — Two-Pass Path Compression:
    • Pass 1 – Root Discovery: Starting from node x, we follow parent[] references until we reach the root r where parent[r] === r. This node r is the representative of the connected component containing node x.
    • Pass 2 – Path Compression: We then walk back along the same path from node x toward the root node r, updating each intermediate node’s parent[] entry to point directly to node r.
    • Effect: This flattening step drastically reduces the number of parent links inside each component, so future find() calls on those nodes become extremely fast.
  • Union(x, y) — Merge by Rank and Update Component Count:
    • To process an edge [x, y], we first compute rootX = find(x) and rootY = find(y). These are the representative roots of the connected components containing node x and node y, respectively.
    • If rootX === rootY, then node x and node y are already in the same component — there is already some path connecting them. In this case, we perform no merge and simply return false to indicate that these two nodes were already in the same component.
    • If rootX !== rootY, then the edge [x, y] connects two different components. We merge these two components into one using union by rank:
      • 🔄 Case 1 — rank[rootX] > rank[rootY]:
        rootX has a higher rank than rootY, so rootX becomes the parent and absorbs rootY’s component. The rank of rootX remains unchanged after the merge. Adding rootY under rootX introduces exactly one additional parent link for the nodes previously rooted at rootY to reach their new root (rootX), but does not go beyond the maximum number of parent links needed to reach rootX within its own component.
      • 🔄 Case 2 — rank[rootX] < rank[rootY]:
        rootY has a higher rank than rootX, so rootY becomes the parent and absorbs rootX’s component. The rank of rootY remains unchanged after the merge. Adding rootX under rootY introduces exactly one additional parent link for the nodes previously rooted at rootX to reach their new root (rootY), but does not go beyond the maximum number of parent links needed to reach rootY within its own component.
      • 🔄 Case 3 — rank[rootX] === rank[rootY]:
        Both roots have equal rank, so we choose rootX as the new root and increment its rank by 1. Since both components have the same maximum number of parent links to their roots, attaching rootY under rootX makes each node in rootY’s component gain exactly one additional parent link to reach their new root. This makes the merged component’s maximum link depth one more than the maximum link depth of the individual components before merging (considering their existing roots before the merge), which is why rank[rootX] is incremented.
      • Since early termination did not happen, it means that rootX !== rootY, so node x and node y belonged to two different components before encountering this edge. Therefore, this edge merges the component containing x with the component containing y according to the union-by-rank rules, and we return true to indicate that a merge occurred.
  • Edge Traversal and Component Counting:
    We let the parameter n serve as our running count of connected components. This works because at the start, each node is the root of its own single-node component.

    Then we iterate over every edge [u, v] in edges:
    • We call union(u, v) to attempt to merge the components containing u and v.
    • If union(u, v) merges two different components (i.e., returns true in the implementation), we decrement n by 1 because two components became one.
    • If union(u, v) determines that u and v were already in the same component before this edge was processed, no merge occurs and n remains unchanged.
    After all edges have been processed, the remaining value of n exactly equals the number of connected components in the graph — which is the final answer.

Time Complexity

For each edge [u, v], we call union(u, v), which in turn invokes two find() operations. With path compression and union by rank, each find() runs in amortized O(α(n)), where α(n) is the inverse Ackermann function (which grows extremely slowly and is effectively constant in practice). The extra work inside union() is O(1). Therefore, processing all edges takes O(m · α(n)) time overall, where m = edges.length, which is usually described as “almost linear” in the size of the input.

Space Complexity

We maintain two arrays, parent[] and rank[], each of size n. Other than these two arrays, only a few temporary variables with constant space usage are needed. Therefore, the overall space usage is O(n).