Skip to content
Hello Python

Trace Disjoint-Set Connectivity

Practice ExerciseAdvancedMediumArrayDisjoint Set Union

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement disjoint_set_trace(node_count, operations). Operations are ["union", a, b] or ["connected", a, b]. Return one boolean per connected query. Use union by size and path compression.

Starter code

def disjoint_set_trace(node_count, operations):
    pass
Test cases

transitive-connectivity

{
  "args": [
    5,
    [
      [
        "union",
        0,
        1
      ],
      [
        "union",
        1,
        2
      ],
      [
        "connected",
        0,
        2
      ],
      [
        "connected",
        0,
        4
      ]
    ]
  ]
}

Expected: [true,false]

redundant-union

{
  "args": [
    3,
    [
      [
        "union",
        0,
        1
      ],
      [
        "union",
        1,
        0
      ],
      [
        "connected",
        0,
        1
      ]
    ]
  ]
}

Expected: [true]

Wizard outline
  1. Step 1: Initialize isolated components

    Give every node itself as parent and answer connectivity by comparing roots. Self-parent roots encode the required initial state before any union.

  2. Step 2: Join two roots

    Handle union by attaching one current root beneath the other. Changing a root parent is the smallest state mutation that creates connectivity.

  3. Step 3: Balance union by size

    Find transitive roots, compress paths, and join smaller components beneath larger roots. A chained union requires root lookup; balancing then keeps that lookup shallow.

Footguns and prerequisites
  • Comparing immediate parents fails when a component contains a multi-level chain.
  • Updating the size of the child root instead of the surviving root breaks union-by-size decisions.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Maintain parent and component-size arrays, find compressed roots, and attach the smaller root to the larger.

Why it works: Each union changes only a root parent, preserving a unique representative per component. Connected returns true exactly when both nodes resolve to that same representative; compression changes paths but never component membership.

def disjoint_set_trace(node_count, operations):
    parent = list(range(node_count))
    size = [1] * node_count
    results = []
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    for operation, left, right in operations:
        if operation == "union":
            left_root, right_root = find(left), find(right)
            if left_root == right_root:
                continue
            if size[left_root] < size[right_root]:
                left_root, right_root = right_root, left_root
            parent[right_root] = left_root
            size[left_root] += size[right_root]
        elif operation == "connected":
            results.append(find(left) == find(right))
    return results