Union-Find: Social Circles in the Internet Age

Union-Find, also known as Disjoint Set Union or DSU, is a data structure for maintaining groups of connected items. It is especially useful when items begin in separate groups and a program repeatedly needs to do two things:

1. Merge the groups containing two items.
2. Determine whether two items belong to the same group.

The social-circle analogy is straightforward. Imagine a network of people. At the beginning, every person is in a separate circle. When two people become connected, their circles may merge. Later, we may ask whether two people are already part of the same circle. Union-Find is designed to answer exactly this kind of question efficiently.

The data structure is built around two fundamental operations:

• Find: determine the representative of the group containing an item.
• Union: merge the groups containing two items.

A basic implementation is easy to understand, but it can become slow when many operations create tall internal trees. Two optimisations address that problem:

• Path compression shortens parent-pointer paths during find.
• Union by rank keeps trees shallow when two sets are merged.

Used together, these optimisations provide near-constant amortized performance. In practical terms, Union-Find is an excellent choice for large sequences of incremental connectivity operations.

1. The problem: maintaining changing groups​

Suppose an online community has five users: A, B, C, D, and E. Initially, no connections have been recorded, so every user forms an independent group:

{A} {B} {C} {D} {E}

If A becomes connected with B, the groups become:

{A, B} {C} {D} {E}

If C becomes connected with D, the groups are:

{A, B} {C, D} {E}

A query such as “Are A and B in the same circle?” should return true. A query such as “Are A and C in the same circle?” should return false.

If C later connects with A, the two groups merge:

{A, B, C, D} {E}

The key property is that these groups are disjoint. Each item belongs to exactly one group at a time. The groups do not overlap, and a merge combines two complete sets into one larger set.

Union-Find is a good match when the main operations are:

• Add a connection between two items.
• Ask whether two items are connected.
• Maintain the connected components created by those connections.
• Optionally track how many separate groups remain.

The connections are commonly treated as undirected relationships. Once two groups are joined, every member of the first group becomes part of the same set as every member of the second group.

2. Representing sets as trees​

Union-Find uses a collection of rooted trees as its internal representation. Each item stores a reference to a parent. A root is an item whose parent is itself.

For five independent items, the parent representation might be:

parent[A] = A
parent[B] = B
parent[C] = C
parent[D] = D
parent[E] = E

Every item is a root, so every item is also the representative of its own singleton set.

After connecting A and B, one possible representation is:

parent[A] = A
parent[B] = A

A points to itself, so A is the root. B points to A, so B belongs to the set represented by A.

If C is connected to D, another tree can be formed:

parent[C] = C
parent[D] = C

The structure now contains separate trees for {A, B}, {C, D}, and {E}.

The trees are not intended to record every original relationship between items. They are an efficient bookkeeping structure for identifying groups. A root acts as the representative of its entire set.

This distinction is important. If B points to A, that does not necessarily mean the original problem contained a direct relationship specifically between B and A. It means that A currently serves as the representative reached by B. Parent pointers are implementation details, not necessarily edges in the original network.

3. The find operation​

The find operation follows parent pointers until it reaches a root. The root is the representative of the item’s group.

Consider this tree:

A
|
B
|
C

The parent relationships are:

parent[A] = A
parent[B] = A
parent[C] = B

To compute find(C):

1. Start at C.
2. Move to C’s parent, B.
3. Move to B’s parent, A.
4. A points to itself, so A is the root.

Therefore, find(C) returns A. Both find(B) and find(A) also return A, so all three items belong to the same set.

A basic recursive implementation looks like this:

find(x):
    if parent[x] == x:
        return x
    return find(parent[x])

The base case identifies a root. If x is not a root, the operation continues with its parent.

An iterative version is:

find(x):
    while parent[x] != x:
        x = parent[x]
    return x

Both versions locate the root. However, these basic forms leave the tree unchanged. If the tree is tall, later searches may have to repeat the same chain of parent-pointer hops.

4. Testing whether two items are connected​

To determine whether two items belong to the same group, find both representatives and compare them:

connected(x, y):
    return find(x) == find(y)

For example, if:

find(A) = A
find(C) = A

then A and C are in the same set.

If instead:

find(A) = A
find(E) = E

then A and E are in different sets.

The program does not need to inspect every member of either group. The representative summarizes the group’s identity for connectivity purposes.

A common mistake is to compare immediate parents rather than roots. Consider:

parent[C] = B
parent[B] = A
parent[A] = A

C belongs to the set represented by A, even though its immediate parent is B. The correct test is:

find(C) == find(A)

It is not correct to compare only parent[C] with parent[A].

5. The union operation​

The union operation combines the groups containing two items. Its usual steps are:

1. Find the root of the first item.
2. Find the root of the second item.
3. If the roots are equal, the items are already in the same set.
4. Otherwise, connect one root to the other.

A basic implementation is:

union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX == rootY:
        return

    parent[rootY] = rootX

Suppose the current sets are:

{A, B} {C, D} {E}

Assume A and C are the roots of the first two sets. Calling union(B, D) works as follows:

• find(B) returns A.
• find(D) returns C.
• A and C are different roots.
• One root is attached below the other.

For example:

parent[C] = A

The two sets are now represented by one tree containing A, B, C, and D.

Union must attach roots, not arbitrary nodes. The roots are the nodes that represent entire sets. By connecting roots, the operation ensures that all members of both sets eventually lead to the same representative.

If the roots are already equal, the union has no structural effect. The operation is still valid, but it does not create a new group or reduce the number of groups.

6. Why a basic implementation can become slow​

The basic representation is correct, but its performance depends on tree shape. If every new root is attached in the same direction, the structure can become a chain:

A
|
B
|
C
|
D
|
E

To find E’s root, the algorithm must visit E, D, C, B, and A. With many items, a chain can make a single find take time proportional to the number of items in the set.

This can happen when a program repeatedly attaches one root below another without considering the height of the two trees. Each union may look simple, but later find operations pay for the accumulated shape.

A tall tree is particularly undesirable because find is used by both connectivity queries and union. A union normally begins by finding two roots, so an inefficient tree can slow down almost every operation.

The performance goal is therefore to keep trees shallow. Union-Find uses two complementary strategies:

• Union by rank controls the shape created during merges.
• Path compression improves paths encountered during searches.

Neither strategy changes group membership. Both modify only the internal parent-pointer structure.

7. Union by rank​

Union by rank chooses which root becomes the parent when two sets are merged. The structure stores a rank value for each root. Rank is related to the tree’s height and is used as a guide for attachment.

The rule is:

• Attach the root with smaller rank below the root with larger rank.
• If both roots have the same rank, choose either root as the new parent and increase that root’s rank.

Pseudocode:

union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX == rootY:
        return

    if rank[rootX] < rank[rootY]:
        parent[rootX] = rootY
    else if rank[rootX] > rank[rootY]:
        parent[rootY] = rootX
    else:
        parent[rootY] = rootX
        rank[rootX] = rank[rootX] + 1

Initially, each item is a one-node tree:

parent[x] = x
rank[x] = 0

When two rank-zero trees are joined, one becomes the parent and its rank increases to one. If a rank-one tree is joined with a rank-zero tree, the rank-one root remains above the rank-zero root, and the rank does not need to increase.

The intuition is that attaching a shorter tree below a taller tree does not make the taller tree deeper. Attaching a taller tree below a shorter one could increase the depth of many nodes, so union by rank avoids that choice.

Rank should be consulted for roots. Non-root nodes may retain old rank values, but once they are attached below another root, their rank no longer determines the representative of a complete set. A correct union operation first calls find and then compares the ranks of the returned roots.

8. Union by size as an alternative​

Union by rank is one way to control tree height. Another related strategy is union by size, which attaches the smaller set below the larger set.

With union by size, each root stores the number of items in its set:

if size[rootX] < size[rootY]:
    parent[rootX] = rootY
    size[rootY] += size[rootX]
else:
    parent[rootY] = rootX
    size[rootX] += size[rootY]

Both strategies follow the same broad principle: avoid putting a larger structure below a smaller one. Rank is intended primarily to guide attachment. Size can guide attachment and also provide useful group-size information.

For example, if an application needs to answer “How many items are in this circle?”, maintaining a size value at each root can make that information available. After a merge, the aggregate size belongs to the new root. A non-root’s stored size should not be treated as the size of the complete current group.

The supplied algorithmic idea is usually described with union by rank, but union by size is a practical alternative. The choice depends partly on whether the application needs set-size information in addition to connectivity.

9. Path compression​

Union by rank limits how tall trees become, but find can improve them further through path compression.

Consider this path:

A
|
B
|
C
|
D

Before compression:

parent[D] = C
parent[C] = B
parent[B] = A
parent[A] = A

A call to find(D) discovers that A is the root. Path compression then redirects each visited node directly to A:

parent[D] = A
parent[C] = A
parent[B] = A
parent[A] = A

The first search still has to traverse the original path. Future searches on B, C, or D can reach A much more directly.

A concise recursive implementation is:

find(x):
    if parent[x] == x:
        return x

    parent[x] = find(parent[x])
    return parent[x]

The assignment is essential. The recursive call obtains the root, and parent[x] is updated to point directly to that root before the result is returned.

An iterative implementation can first locate the root and then compress the path in a second pass:

find(x):
    root = x

    while parent[root] != root:
        root = parent[root]

    while parent[x] != x:
        nextNode = parent[x]
        parent[x] = root
        x = nextNode

    return root

The exact implementation can vary, but the purpose is the same: nodes encountered during a search become closer to the representative.

10. Why path compression is safe​

Path compression may appear to change the groups, but it does not. It changes only the route used to reach a root.

Before compression:

D -> C -> B -> A

The set represented by A contains D, C, B, and A. After compression:

D -> A
C -> A
B -> A

The same four items remain in one set, and A is still the representative. The only difference is that future searches require fewer pointer hops.

This illustrates a useful data-structure principle: an internal representation can be reorganized without changing the logical result. Union-Find takes advantage of that flexibility to improve performance over time.

Path compression also explains why an amortized analysis is appropriate. An individual find may encounter a path that has not yet been shortened, but the work it performs improves the structure for later operations.

11. Combining both optimisations​

The standard high-performance Union-Find implementation uses path compression and union by rank together:

find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX == rootY:
        return

    if rank[rootX] < rank[rootY]:
        parent[rootX] = rootY
    else if rank[rootX] > rank[rootY]:
        parent[rootY] = rootX
    else:
        parent[rootY] = rootX
        rank[rootX] = rank[rootX] + 1

The two techniques solve different parts of the problem:

• Union by rank prevents merges from repeatedly creating unnecessarily tall trees.
• Path compression flattens the paths that queries actually traverse.

They work together rather than replacing one another. Rank gives the structure a good shape during merges, while path compression improves the particular routes used by searches.

With both optimisations, a sequence of m operations on n items has near-constant amortized cost per operation. The common formal bound is O(alpha(n)) amortized per operation, where alpha is the inverse Ackermann function. This function grows so slowly that, for practical input sizes, the cost is effectively near O(1).

The term amortized matters. It does not claim that every individual find takes exactly constant time. Instead, it describes the average cost over a sequence of operations. A search that performs more work can shorten the structure and make later searches cheaper.

12. A complete example​

Consider five users: A, B, C, D, and E. Initially:

parent[A] = A
parent[B] = B
parent[C] = C
parent[D] = D
parent[E] = E

Every user is in a separate set.

Step 1: union(A, B)​

The roots are A and B. Their ranks are equal, so choose A as the new root and increase its rank:

parent[B] = A
rank[A] = 1

The sets are now {A, B}, {C}, {D}, and {E}.

Step 2: union(C, D)​

The roots are C and D, again with equal ranks. Choose C as the root:

parent[D] = C
rank[C] = 1

The sets are {A, B}, {C, D}, and {E}.

Step 3: union(B, D)​

The operation does not attach B directly to D. It first finds their roots:

find(B) = A
find(D) = C

The roots A and C have equal rank. Choose A as the new root and increase its rank:

parent[C] = A
rank[A] = 2

The conceptual tree is:

    A
   / \
  B   C
      |
      D

The sets are now {A, B, C, D} and {E}.

Step 4: find(D)​

D points to C, and C points to A. The root is A. Path compression changes D’s parent to A:

parent[D] = A

The tree is flatter:

    A
  / | \
 B  C  D

Step 5: connected(A, D)​

The operation compares:

find(A) = A
find(D) = A

The result is true.

Step 6: connected(A, E)​

The operation compares:

find(A) = A
find(E) = E

The result is false.

This example shows the complete lifecycle: independent singleton sets, group merging, root discovery, path compression, and connectivity queries.

13. Tracking the number of groups​

A Union-Find structure can maintain the number of disjoint groups. If there are n items, the initial number of groups is n. Every successful union reduces the count by one.

A union is successful only when the two roots are different. If the roots are already equal, the items are already in the same group and the count must not change.

Pseudocode:

initialize n items
components = n

union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX == rootY:
        return

    attach one root below the other
    components = components - 1

With five initial items, the count starts at five. After joining A with B, it becomes four. After joining C with D, it becomes three. Joining B with D merges two existing groups, so it becomes two. Calling union again on A and C does not change the count because those items already share a root.

This counter is a useful application-level addition. It allows the program to maintain a global summary while processing individual connections.

14. Initialization and item identifiers​

A practical implementation needs a parent and rank entry for every item. If items are represented by integer identifiers from zero through n - 1, arrays are a natural choice:

for x from 0 to n - 1:
    parent[x] = x
    rank[x] = 0

If the input uses names such as usernames or labels, those names can be mapped to integer identifiers. The Union-Find structure then operates on the identifiers while a separate mapping preserves the original labels.

The initialization rule is fundamental: every item starts as its own parent. If an item were initialized with a different parent before a connection had been processed, the structure would incorrectly report that the item already belonged to another set.

When a new item is added dynamically, initialize it as a singleton set:

parent[newItem] = newItem
rank[newItem] = 0

The surrounding implementation also needs to account for the new item when tracking the number of components.

15. Common implementation mistakes​

Comparing parents instead of roots​

Two items may have different immediate parents but still belong to the same set. Always compare find(x) with find(y).

Attaching arbitrary nodes during union​

Union should connect the roots returned by find. Attaching arbitrary nodes can produce incorrect representative relationships or an invalid structure.

Forgetting the compression assignment​

This code finds the root but does not compress the path:

return find(parent[x])

The compressed version stores the returned root:

parent[x] = find(parent[x])
return parent[x]

Without the assignment, the algorithm can remain logically correct, but it loses the main benefit of path compression.

Updating rank after every union​

Rank should increase when two roots have equal rank and one is attached below the other. If a lower-rank tree is attached below a higher-rank tree, the higher rank does not need to increase.

Increasing the component count for redundant unions​

A union between two items already in the same set does not merge two groups. Decrease the component count only when the roots differ.

Treating parent pointers as direct relationships​

The parent tree is an internal representation. A parent pointer does not necessarily correspond to a direct connection in the original network.

Ignoring recursion depth​

The recursive form of find is concise, but a language with a limited call stack may motivate an iterative implementation. The algorithmic idea is unchanged; only the traversal style differs.

16. When Union-Find is a good fit​

Union-Find is a strong fit when relationships are added over time and the required questions concern whether items are in the same connected group.

Typical patterns include:

• Processing a sequence of pairwise connections.
• Tracking social circles or connected communities.
• Maintaining connected components as links are added.
• Checking whether a new connection joins previously separate groups.
• Determining whether two items have become connected.
• Counting how many disjoint groups remain.

The shared pattern is incremental merging. Each successful union combines two sets, and the data structure is particularly good at handling repeated merges and connectivity checks.

17. When another structure may be better​

Union-Find is not a complete graph representation. It focuses on component membership, not on preserving every detail of the connection network.

If a program needs to enumerate a node’s neighbors, an adjacency list is more appropriate. If it needs shortest paths, a graph traversal or shortest-path algorithm may be required. If connections can be removed frequently, the standard Union-Find design is not directly suited to undoing arbitrary merges, because a union changes parent relationships and path compression may also change the structure.

Union-Find also does not naturally describe overlapping groups. Its fundamental assumption is that each item belongs to one disjoint set at a time.

A practical selection rule is:

Use Union-Find when the core question is whether two items belong to the same connected component after processing the connections seen so far.

Use a richer graph structure when the actual paths, neighbors, edge properties, or changing removals matter.

18. Detecting redundant connections​

A useful application of connectivity testing is identifying whether a proposed connection joins two items already in the same group.

For each pair (x, y):

1. Find the root of x.
2. Find the root of y.
3. If the roots match, the connection is redundant with respect to connectivity.
4. Otherwise, union the two roots.

This approach does not require searching through every existing relationship. The roots summarize current component membership. A connection between different components merges them; a connection within one component does not change the number of components.

This is also a useful way to understand incremental connectivity. Every incoming pair can be classified using the same two operations: find both representatives, then merge only if the representatives differ.

19. Debugging a Union-Find implementation​

When debugging, inspect the parent and rank arrays after each operation. For every root, verify:

parent[root] == root

For every non-root item, repeatedly following parent pointers should eventually reach a root. If parent pointers form a cycle, the structure is corrupted.

A useful manual test is:

1. Initialize several singleton items.
2. Connect two pairs independently.
3. Verify that each pair has a shared root but the pairs have different roots.
4. Connect one item from each pair.
5. Verify that all four items now have the same root.
6. Run find on a deeper member and inspect whether its parent was shortened.
7. Call union on two members of the same group and verify that the component count does not change.

Tests should include successful unions and redundant unions. They should also query roots, direct children, and nodes several levels below a root.

When using rank, verify that comparisons are made after finding roots. When using path compression, verify that the root returned by the recursive call is assigned back to the current node’s parent.

20. Complexity intuition​

Without optimisations, a tree can become a long chain, and a find operation may take linear time in the number of items in that component. Repeated operations can therefore become expensive.

Union by rank prevents the tree from growing arbitrarily through careless attachment. Path compression makes paths shorter as they are used. Together, they provide near-constant amortized performance for union and find operations.

A common formal summary is:

• Initializing n items takes O(n) time.
• A sequence of operations using union by rank and path compression takes near-constant amortized time per operation.
• The total cost of m operations on n items is commonly described as O(m alpha(n)).

Here, alpha is the inverse Ackermann function, which grows extraordinarily slowly. For practical software engineering purposes, the important conclusion is that the combined structure is extremely efficient for large sequences of connectivity operations.

The distinction between a single-operation bound and an amortized sequence bound should be retained. The guarantee concerns the overall sequence, not a promise that every individual call has exactly the same constant cost.

21. A compact class design​

A typical Union-Find class stores three pieces of state:

parent
rank
components

The responsibilities can be separated clearly:

constructor(n):
    parent = array of length n
    rank = array of length n filled with zero
    components = n

find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX == rootY:
        return false

    attach the lower-rank root below the higher-rank root
    update rank when ranks are equal
    components = components - 1
    return true

connected(x, y):
    return find(x) == find(y)

Returning a Boolean from union is convenient. true can mean that two separate sets were merged, while false can mean that the items were already connected. This return value can drive component counting or redundant-connection detection.

The exact programming-language syntax may differ, but this division keeps the algorithm easy to test. find manages representative discovery and compression. union manages merging. connected exposes the main query in readable form.

22. Understanding representatives​

A representative is chosen by the implementation. If two separate runs process the same logical connections in different orders, they may choose different roots while still producing exactly the same group membership.

For correctness, the important condition is:

find(x) == find(y)

if and only if x and y are in the same set.

The identity of the representative may change when two groups are united. Code using Union-Find should therefore treat the root as an implementation-level identifier rather than as a permanent user-facing label for a group.

If a stable external group name is required, it should be managed separately. Union-Find’s representative is optimised for connectivity operations, not necessarily for display or naming.

23. Translating a problem into operations​

When reading a problem statement, translate its language into Union-Find operations:

• “These two items become connected” usually suggests union(x, y).
• “Are these items in the same group?” suggests connected(x, y).
• “Which group contains this item?” suggests find(x).
• “How many groups remain?” suggests maintaining a component counter.

The order of operations matters because Union-Find represents the state accumulated so far. A query reflects only the connections that have already been processed. If the input describes a chronological sequence, process it in that sequence.

This translation step is often more important than the implementation details. Once a problem is recognised as disjoint-set maintenance, the data structure provides a direct vocabulary for solving it.

24. Practical takeaways​

Union-Find can be remembered through a small set of rules:

1. Start every item in its own set.
2. Store each item’s parent.
3. A root points to itself.
4. find follows parent pointers to a root.
5. union first finds both roots.
6. If the roots match, the sets are already joined.
7. Otherwise, attach one root below the other.
8. Use union by rank to keep trees shallow.
9. Use path compression to flatten paths during find.
10. Reduce the group count only when two different roots are merged.

The social-circle metaphor captures the purpose: new relationships merge separate circles, and representative lookup tells us whether two people are already in the same circle. The tree representation makes those operations efficient, while the two optimisations ensure that the internal structure improves as it is used.

Conclusion​

Union-Find is a focused data structure for maintaining disjoint groups under repeated connections and connectivity queries. Its two fundamental operations are simple: find identifies a set’s representative, and union merges the sets represented by two different roots.

The basic parent-pointer representation explains the idea, but careless unions can produce tall trees. Union by rank avoids attaching taller trees below shorter ones, while path compression redirects searched nodes directly to the root. Together, these techniques provide near-constant amortized performance, making Union-Find highly practical for large sequences of group-merging operations.

Whenever a problem describes items that start separately, become connected over time, and must be checked for shared membership, Union-Find should be one of the first data structures to consider.