# Disjoint Set — Union & Find

Sep 16, 2020 · 4 min read

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.

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 `v`belong 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…

Written by

Be a hero!

## Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

Written by

Be a hero!

## Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

## 5 Must-Have Python Developers Skills To be Successful

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