Leetcode-Union-Find Data Sturcture

2 min readJun 2, 2020

A Union-Find data structure also called Disjoint set data structure is to maintain a set of elements partitioned into a number of mutually disjoint(non-overlapping) subsets. So, no elements belong to more than one set.

Definition:

In Union-Find data structure, each subset represent a backwards tree with pointer from a node to its parent and nodes in the tree are elements of this subset [1].

Properties:

The Union-Find data structure that efficiently support two operations

Find: Given a node u, to find root node of u.
Union: Given two nodes u and v, to merge them together if they’re disjoint. Otherwise, return False, which means they’re connected already.

Check whether two elements are in the same set by find function in O(log(n)*)≃ O(1), amortized time complexity.

Applications:

connected component in Graph problem
detecting cycles in graph.
minimum spanning tree

Implementation with an example:

There’re a couple ways to implement Union-Find with corresponding different time complexity[2]:

union-by-size, O(log(n))
union-by-height, O(log(n))
union-by-rank with path compression, O(log(n)*)≃ O(1) [4].

Note:

It’s relatively rare to be used in Leetcode problems and sometimes it could be replaced with DFS solution. However, it can solve problem more efficiently.
How to implement [3]? Please see my code in below leetcode problems.
In order to use union-find data structure to solve problem, we need to convert each node to index ranging from 0 to n-1(totally, n nodes in the graph)

The below problems related to Union-Find in leetcode: