Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 63 ยท Data Structures in Contest Practice

DSU and Tree Problems

Contest guide to union-find with path compression, Kruskal's MST, weighted DSU for difference constraints, and tree traversal without recursion in Python.

A disjoint set union (DSU, also called union-find) answers one question quickly: "are these two items in the same group?", while groups merge over time. It is tiny to code, nearly constant time per operation, and sits behind component counting, Kruskal's minimum spanning tree, offline connectivity and many "merge these two things" statements. Trees are the other half of this lesson: contest inputs often give n - 1 edges and expect you to compute parents, depths, subtree sizes and ancestor relationships, in Python without running into the recursion limit.

The structure and its analysis are explained in Union-Find and Minimum Spanning Tree. Here we write the contest versions: iterative find, a weighted variant for difference constraints, and tree walks that never recurse.

A contest-ready DSU

Store parent[i] (initially i) and size[i] for roots. find(x) follows parents to the root and compresses the path so later calls are shorter. union(a, b) attaches the smaller tree under the larger and returns whether a merge happened.

Write find iteratively. A recursive find on a long chain hits Python's recursion limit, and raising the limit risks crashing the interpreter. Two passes are enough: one to find the root, one to point every node on the path directly at it.

With path compression and union by size, the amortized cost per operation is the inverse Ackermann function, which is at most 4 for any input that fits in the universe. Treat it as constant.

Useful extras to keep on the object: the number of components (decrement it on every successful union) and the size of each component (read size[find(x)]).

Python DSU with components, sizes and a connectivity check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Kruskal's minimum spanning tree

A spanning tree connects all n vertices with n - 1 edges and no cycle. The minimum one (smallest total weight) is found greedily: sort the edges by weight and take an edge whenever its endpoints are still in different components. The DSU is exactly the "are they connected?" test. Complexity is O(m log m) for the sort.

flowchart LR
    A["Sort edges by weight"] --> B["Next edge (u, v, w)"]
    B --> C{"find(u) == find(v)?"}
    C -->|yes| D["Skip: would form a cycle"]
    C -->|no| E["Union and add w"]
    D --> B
    E --> B

Kruskal's loop: a DSU rejects the edges that would close a cycle.

If the graph is disconnected, you end with fewer than n - 1 accepted edges: a minimum spanning forest. Check components when the statement says "if the network cannot be connected, print -1".

Variants that appear often: the maximum spanning tree (sort in reverse), "the minimum possible largest edge so that the graph is connected" (the last edge Kruskal accepts is the answer), and "connect with the fewest new edges" (answer components - 1).

Weighted DSU: relations between items

Sometimes the group carries more than membership. A statement gives facts of the form "value of B minus value of A is w" and asks whether the facts are consistent, or what the difference between two items is. A weighted DSU stores, for every node, its offset from its parent: diff[x] = value(x) - value(parent[x]). After path compression, diff[x] is the offset from the root.

  • find(x) compresses and accumulates offsets along the path.
  • To merge with the fact value(b) - value(a) = w: find roots ra, rb with offsets da = value(a) - value(ra) and db = value(b) - value(rb). If the roots are equal, the fact is consistent exactly when db - da == w. Otherwise attach rb under ra with diff[rb] = w + da - db.
  • To answer "what is value(b) - value(a)", if they share a root it is diff[b] - diff[a]; otherwise it is unknown.

The same pattern handles "same or different team" parity constraints (offsets modulo 2), ratios (multiply offsets), and potentials in difference-constraint puzzles.

Python Kruskal and a weighted DSU

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trees without recursion

A tree given as n - 1 undirected edges has no direction until you root it. One loop with an explicit stack computes everything you need:

  1. Build adjacency lists.
  2. Start at the root, pop a node, record it in order, and push each neighbor that is not its parent while setting parent and depth.
  3. Subtree sizes: walk order backwards and add each node's size to its parent. In reverse order, every child is processed before its parent.
  4. Entry and exit times (tin, tout) need a true DFS where a node is "closed" after all its children. With them, u is an ancestor of v exactly when tin[u] <= tin[v] < tout[u], and the subtree of u is the contiguous slice tin[u]..tout[u]-1 of the DFS order, which turns subtree queries into range queries (prefix sums or a Fenwick tree).

Why not recursion? A path-shaped tree with 10^5 nodes means recursion depth 10^5, and CPython's default limit is about a thousand. Increasing it works on many judges but can crash with a segmentation fault. An explicit stack has no such limit.

Python Parents, sizes and Euler times without recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing between BFS, DFS and DSU

Task Best tool
Count components in a fixed graph DSU or BFS, either is fine
Edges arrive over time, query connectivity DSU (BFS would redo work)
Edges are also deleted Offline tricks, not plain DSU
Minimum spanning tree Kruskal with DSU
Facts like "A is w more than B" Weighted DSU
Subtree sums or sizes in a rooted tree Reverse of the traversal order
"Is u an ancestor of v?" Entry and exit times

Pitfalls

  • Reading edges as 1-based while using 0-based arrays is the most common source of runtime errors. Subtract one at input time, once.
  • Forgetting to compare roots (find) and comparing raw parents instead.
  • In weighted DSU, update offsets in the right order when compressing; process nodes from nearest the root outward.
  • A tree has n - 1 edges. If the edge count differs, the input is a forest or contains a cycle.
  • Recursion in tree code is fine for small n and fatal for chains. If the constraints allow n near 10^5, write the iterative version from the start.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which two optimizations make a DSU run in nearly constant amortized time?

    Union by size keeps trees shallow and path compression flattens them during finds. Together they give the inverse Ackermann bound.
  2. 2. In Kruskal's algorithm, when is an edge (u, v) skipped?

    If both endpoints are already connected, adding the edge creates a cycle, which a spanning tree cannot contain.
  3. 3. A graph has 10 vertices and 3 components. Minimum number of new edges needed to make it connected?

    Each added edge can merge at most two components, so going from 3 components to 1 needs 3 - 1 = 2 edges.
  4. 4. How do you test whether u is an ancestor of v using entry time tin and exit time tout?

    All descendants of u are visited between its entry and exit, so v is inside u's subtree exactly when tin[v] falls in that interval.
  5. 5. Why compute subtree sizes by walking the traversal order in reverse?

    A node is appended to the order before its descendants, so in the reversed order all descendants come first and can add their sizes into the parent.

Summary

  • A DSU with iterative path compression and union by size handles merges and connectivity queries in nearly constant time.
  • Track the component count and component sizes as you merge.
  • Kruskal: sort edges, accept an edge when its endpoints are in different components; the accepted weight is the MST weight.
  • A weighted DSU stores offsets to answer and validate difference constraints.
  • Root a tree with an explicit stack, compute sizes in reverse traversal order, and use entry/exit times for ancestor and subtree queries.
  • Never rely on recursion for chain-shaped inputs in Python.

Next: Fenwick and Segment Trees for Contests