Disjoint sets

This is one important concept for grouping problems. I read all, then started doing the first problem and confused like how to do it.

This concept is related to graphs or not graphs but there are a set of nodes or vertices where some vertices are grouped and some or not, means some are not joined or some are disjoined :). So to find these disjoint nodes or disjoint vertices, this disjoint sets data structure is useful.

This disjoint sets data structure consists of an array elements (root array) where each element corresponding to each vertex. This array element either points to itself or points to parent vertex or points to root vertex. This implementation can also consists of rank array indicating the rank of each vertex. This is used in optimization.

There are 4 functions:

  • Initialization: Each array element in root array is initialized to the corresponding vertex value. Each element in rank array is initialized to 1. Pseudo code:
  • Find(): There are different implementations of it. Below is the optimized version. The purpose of this function is to return the root node of a given vertex.

This above function tries to find the root/parent of the vertex and also update to the root value.

  • Union(): There are different implementations to this function. Below is the optimized version. The purpose of this function is to join the given vertices (x,y) as making one vertex as another vertex’s parent and setting the root of the node to the corresponding vertex:
  • Connected(): The purpose of this function is to check if the given vertices are connected (or joined or disjoined).

Eg: (0,4),(1,5),(4,12),(5,12) are given.

(0,4)==> setting root[4] to 0

(1,5)==> setting root[5] to 1

(4,12) ==> setting root[12] to 0

(6,11)==> setting root[11] to 6

(6,12)==> setting root[6] to 0,

(11,12)==> setting root[11] to 0

Number of Provinces

Below is the problem stmt:

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Even though I learned the above disjoint sets concept, again I was thinking how to find. This problem is to check how many disjoint sets are there :)

Based on the 2 d array, frame a disjoint set and then check how many disjoint sets are there (with root values). Below is the solution:\

Please give your comments.

--

--

www.linkedin.com/in/jyothivs

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