Have you ever wondered how to group connected components in a graph and check whether two nodes belong to the same group? That’s exactly where Union-Find(also called Disjoint Set Union or DSU) comes into play.

Let’s understand this through a real example — solving the Number of Good Pathsproblem using Union-Find.

✨ What is Union-Find?

Union-Find is a smart way to:

  • Group items together (called sets)
  • Find whether two items belong to the same group (or set)
  • Merge two groups together (union)

It’s widely used in problems where you need to track connected components — especially in graphs.

💡 When to Use Union-Find?

Look for patterns like:

  • “Are these two nodes connected?”
  • “How many groups/components exist?”
  • “Merge if two nodes have some condition met”
  • “Check cycles in undirected graphs”
  • “Build groups with some rules/conditions”

If the problem talks about connected nodes, merging subsets, or tracking isolated components, Union-Find is likely the tool you need!

🚩 Problem Intuition: Number of Good Paths

📌 Problem:

Given a tree (undirected graph) and a value for each node, you must count all “good paths”.
A good path is a path where:

  • The start and end values are equal
  • All the values on the path are less than or equal to this value

🧠 Intuition:

  • Every single node is a valid “good path” (path of length 0).
  • Suppose a node has the maximum value v, and there are k such nodes, then we can form k*(k-1)/2 pairs among them. Each pair is a valid good path.
  • But these nodes must be connected. That’s where Union-Find helps us to build and track connected components.

🔁 How Does the Algorithm Work?

We solve this bottom-up, not by cutting the tree but by joining smaller value nodes first.

Step-by-step:

  1. Initialize each node as its own set using Union-Find.
  2. Sort all edges by the maximum value of the two connecting nodes.
  3. For each edge (i, j) with value v:
    • If vals[i] <= v and vals[j] <= v, try to merge their sets.
    • If both ends have the same value v, we can form new good paths = count[i] * count[j].
  4. Update the parent and value count using Union-Find.
  5. Keep adding new good paths to the result.

🧮 Python Code (with Explanation)

from collections import Counter

def numberOfGoodPaths(vals, edges):
    n = len(vals)
    res = n  # Every single node is a good path

    parent = list(range(n))  # DSU parent
    count = [Counter({vals[i]: 1}) for i in range(n)]  # Count of value v in each set

    # Sort edges based on max value of the two connecting nodes
    edges = sorted([max(vals[i], vals[j]), i, j] for i, j in edges)

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]

    for v, i, j in edges:
        pi, pj = find(i), find(j)
        if pi == pj:
            continue

        # Get count of value `v` in both sets
        ci, cj = count[pi][v], count[pj][v]

        # Number of good paths is combinations of ci and cj
        res += ci * cj

        # Merge sets
        parent[pj] = pi
        count[pi] += count[pj]

    return res

⏱️ Time and Space Complexity

  • Time: O(n * α(n)) where α(n) is the inverse Ackermann function (very small)
  • Space: O(n) for parent tracking and value counting

🧠 Key Takeaways

  • Union-Find is a perfect choice when you need to group and check connectivity efficiently.
  • Look for “can be connected” + “same condition” patterns — Union-Find will likely help!
  • This problem smartly builds sets from smaller values upward and uses merging to track connected values.