Union Find: Connected Components

One representative per component

Each root points to itself. Following parent pointers reaches the representative of a component. Two nodes are connected exactly when their representatives match.

Only root sizes are authoritative. Union by size attaches the smaller component's root to the larger one's root. Path compression makes the nodes visited by find point directly to their representative. Neither optimization changes which elements are connected.

• Compare representatives, not immediate parents.
• Decrease the component count only when two different roots merge.
• The chosen root can change. Do not give its numeric ID domain meaning.

Keep this standalone template handy

Use dense indices 0 through n-1. Map string identifiers to indices before constructing the DSU when necessary. The public method names match the Accounts Merge solution. The reusable class stores only parents and sizes.

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (unused, index) => index);
    this.size = new Array(n).fill(1);
  }

  findUnionParent(node) {
    if (this.parent[node] === node) return node;
    this.parent[node] = this.findUnionParent(this.parent[node]);
    return this.parent[node];
  }

  unionBySize(u, v) {
    let uParent = this.findUnionParent(u);
    let vParent = this.findUnionParent(v);
    if (uParent === vParent) return false;

    if (this.size[uParent] < this.size[vParent]) {
      [uParent, vParent] = [vParent, uParent];
    }
    this.parent[vParent] = uParent;
    this.size[uParent] += this.size[vParent];
    return true;
  }
}

• unionBySize returns false for an already-connected pair. Duplicate connections do not change sizes or counts.
• If a problem needs the number of groups, keep let components = n outside the class. For each connection, use if (dsu.unionBySize(u, v)) components--. Problems that only group elements do not need this counter.
• Use findUnionParent again when grouping results: an earlier representative may have been attached to another root.
• Union by size bounds parent-chain depth by O(log N) even before compression. This recursion is not the same risk as walking an arbitrary 100000-node input chain.

Trace merges without confusing roots and edges

This walkthrough also tracks an optional component count outside the DSU. Start it at n and decrease it only when unionBySize returns true.

In Accounts Merge, a shared email supplies evidence that two account indices belong to one component. The same name alone is not evidence. Deduplicate emails before producing sorted output.

For timestamped friendship events, sort by time, union each pair, and stop when the component count reaches one. The sorting cost is separate from DSU operations.

1. Begin with four roots: components = 4 and sizes are all 1.
2. unionBySize(0,1) creates {0,1}; components = 3.
3. unionBySize(2,3) creates {2,3}; components = 2.
4. unionBySize(1,2) joins the two representatives; components = 1.
5. unionBySize(0,3) returns false because they already share a representative.

When a traversal is the better tool

Path With Maximum Minimum Value can activate cells in descending value order and union adjacent active cells. The first value at which start and end become connected is the threshold. That approach must also pay for sorting; a priority queue offers a different implementation.

Separate DSU cost from the rest of the problem

• Initialization uses O(N) time and space.
• Union by size with path compression gives O(alpha(N)) amortized time per find or union across a sequence of operations. alpha is the inverse Ackermann function; this is not a worst-case O(1) guarantee for every call.
• Sorting E events costs O(E log E); grouping and sorting account emails adds its own cost.
• Update size at the receiving root with +=. Assigning the smaller size instead corrupts the weighting heuristic.

Mistakes and Counterexamples