Union and Find

This page provides introduction to union and find data structure.

Overview

Union and find is a data structure used to efficiently manage a collection of disjoint sets and supports two main operations:

• Union: Merges two sets into one.
• Find: Determines which set a particular element is in.

Build Union and Find

Let's build a union and find data structure for below disjoint group:

We represent all relationships in disjoint groups using the union and find data structure. To achieve this, we first determine the parent of each node by tracing the values in the array until we find a node that points to itself. Once the parents are identified, we unify the groups by assigning the parent of one node to the other.

Initially, we set the parent of each node to itself.

Node $0$ is connected to node $1$. The parent of $0$ is $0$, and the parent of $1$ is $1$. Therefore we update the parent of $1$ to be $0$ to represent the connection.

Node $0$ is connected to node $3$. The parent of $0$ is $0$, and the parent of $3$ is $3$. Therefore we update the parent of $3$ to be $0$ to represent the connection.

Node $1$ is connected to node $0$. The parent of $0$ is $0$, and the parent of $1$ is $0$, here no updates are required and node $0$ and $1$ belong to same group.

Node $1$ is connected to node $2$. The parent of $1$ is $0$, and the parent of $2$ is $2$. Therefore we update the parent of $2$ to be $0$ to represent the connection.

Similarly, we explore all connections from node $2$ and $3$ to get the same result as above image.

Next we explore all connections from node $4$. The parent of $4$ is $40$, and the parent of $5$ is $5$. Therefore we update the parent of $5$ to be $4$ to represent the connection.

Similarly, we explore all the connections from node $5$ to get the same result as above image.

Finally, we visit node $6$, which has no connections, and our union-find data structure is complete, representing $3$ disjoint groups.

Java

class UnionAndFind {
  int[] parentArr;

  UnionAndFind(int nodes) {
    this.parentArr = new int[nodes];
    for(int i = 0; i < nodes; i++) {
      parentArr[i] = i;
    }
  }

  public void union(int from, int to) {
    int fromParent = find(from);
    int toParent = find(to);
    if(fromParent != toParent) parentArr[fromParent] = toParent;
  }

  public int find(int node) {
    if(parentArr[node] == node) return node;
    int parent = parentArr[node];
    /**
     * Path compression: Since we have already calculated the parent for this node, 
     * we can directly update it in the parent array. 
     * This helps reduce the time required for future queries.
     */
    return parentArr[parent] = find(parent);
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

The time complexity for find is:

$$\text{O}(\alpha\text{(N))}$$

Where, $\alpha\text{(N)}$ is the inverse Ackermann function.

info

The Ackermann function grows extremely slowly, and for practical purposes, $\alpha\text{(N)}$ is close to a constant value Thus, the find operation is nearly constant time in practice $\text{O(1)}$ for most cases.

It requires at most one find operation for each of the two sets being merged therefore the time complexity for union is:

$$\text{O}(\alpha\text{(N))}$$

Space Complexity

The space is required to store the parent pointers of each element, therefore space complexity is:

$$\text{O(N)}$$

Leetcode Problem Set