Disjoint Set — Union & Find

OnePunch
OnePunch
Sep 16, 2020 · 4 min read

Source: https://shawnlyu.com/algorithms/disjoint-set-union-find/

In computer science, a disjoint-set data structure … is a data structure that stores a collection of disjoint (non-overlapping) sets. … It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set.

Source: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Disjoint Set helps to group distinct elements into a collection of disjoint sets. There are two major functions associated with it: finding the set that a given element belongs to and merging two sets into one (Cormen, Thomas H., and Thomas H. Cormen. Introduction to Algorithms). This post will introduce the implementations of two functions union(u,v) and find(p), and provide more details using Leetcode 200. Number of Islands as an example.

find(p), union(u,v), and optimization

There are two optimizations in the two functions: path compression and merge by rank.

find(p) and path compression

Given an element p, find(p) will return the representative of the set that p belongs to. Initially, we have an array root indicating the root of each element. Therefore, we can recursively or iteratively search for the root of p through root.

We can add path compression as optimization. While we are searching for the root of p, we can assign the root to the elements along the path. Also there will be two ways of implementing this.

union(u,v) and merge by rank

Given two elements u and v, union(u,v) merges the sets that u and vbelong to accordingly into one. To avoid the case shown below, we can add merge by rank as optimization.

We can have an array rank indicating the height of each node and when we merge two sets, we would always seek to put the set with lower rank under the set with a higher rank.

Complexities

Without path compression and merge by rank, the time complexity for find(p) could be O(n)O(n) and

Leetcode 200. Number of Islands

Initially, we would assign all '1' element as an isolated island. While we are iterating from top to bottom and from left to right, if we find its right neighbour or its neighbour below is also '1', we can conduct union(u,v). Remember to deduct 1 from the total number of the island when we merge two sets.

Reference

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store