Union-Find (Disjoint Set)

    DSA · Advanced

    Definition

    Union-Find tracks which elements belong to the same group with find and union operations.

    Used for connected components, cycle detection and Kruskal's algorithm.

    Diagram

    1 → 12 → 13 → 14 → 4

    Flowchart

    Each node is its own parentfind follows parents to rootunion links two rootsPath compression flattens trees

    Example: Count components

    p = list(range(5))
def find(x):
    while p[x] != x:
        p[x] = p[p[x]]
        x = p[x]
    return x
for a, b in [(0, 1), (1, 2), (3, 4)]:
    p[find(a)] = find(b)
print(len({find(i) for i in range(5)}))

    Output: 2

    Complexity

    Nearly O(1) amortized per operation (α(n))

    Key points

    • Use union by rank + path compression
    • Detects cycles in undirected graphs

    Interview questions

    How does it detect a cycle?

    If both ends of an edge already share a root, adding it forms a cycle.

    More DSA topics

    ArraysLinked ListStackQueue