Lecture_Notes/articles/Akash Articles/md/DSU.md

Suppose, you are giving a programming contest and one of the problem is: You are given a number of vertices and a list of undirected unweighted edges between these vertices. Now the queries are to find whether there is a path from some vertex u to v. Note that the whole graph may not be connected. How can you solve it?

DFS, Right? Start DFS from either u or v and check if we can reach to the other vertex. Done!

But what if the graph is dynamic, means that apart from the path query, you are given another type of query which is, to add an edge in the graph. Now, how to solve it?

Again DFS? Yes, you can add any number of edges and still check if there is a path from vertex u and v. But if you do that then you will get TLE(Time limit exceed).

Now, Disjoint Set Union is a data structure which can do this operations very efficiently.

But what do we mean by the name "Disjoint Set Union". Set is a collection of distinct elements. Disjoint set means they are non-overlapping - in language of math if A and B are two disjoint sets then A \cap B = \phi. Union is an operation, we do to combine two disjoint sets.

In the above stated problem, we can consider a connected components as disjoint sets and then we can do union when we are adding edges.

For the queries, to check if there is a path from u to v, we can check whether u and v are in the same disjoint sets, if yes then there is a path from u to v, otherwise not. Confusing?

Now, let's see how it works actually.

Disjoint Set Union

Disjoint Set Union is one of the simplest and easy to implement data structure, which is used to keep track of disjoint(Non-overlapping) dynamic sets.

There are three main operations of this data structure: Make-set, Find and Union

1. Make-Set: This operation creates a disjoint set having a single element.

2. Find: This operation finds a unique set to which a particular element belongs.

3. Union: This operation unifies two disjoint sets.

There are many ways we can implement this data structure: Linked list, Array, Trees. But here we will implement it using array and represent using tree.

Some Terminologies

• Parent is a main attribute of an element(or set), which represents an element by which a particular element is connected with some disjoint set. In the image below, c is parent of d and a is parent of c.

  Note: Below is just for visualization purpose, if you don't understand it right now. Don't worry, you will understand it by the end of the article.

• Root is an element of a set whose parent is itself. It is unique per set. a is the root element for the disjoint set above in the image.

Operation Make-Set

Make-Set operation creates a new set having a single element (means size=1) which is having a unique id.

Pseudocode:

MAKE-SET(x)
{
	x.parent = x;
	x.size = 1;
}

Here X is the only element in the set so it is parent of itself.

The image below represents sets generated by this operation. Where each one having arrow coming to itself, which represents that it is its own parent right now. Each one has size of 1.

We are working with arrays, so the code to make n sets is as below:

vector<int> parent,size;
void Make_sets(int n)
{
	parent.resize(n);
	size.resize(n);
	for(int i = 0; i < n; i++)
	{
		parent[i] = i;
		size[i] = 1;
	}
}

Time Complexity: Make-Set operation takes O(1) time. So to creat N sets it will take O(N) time.

Operation Find

\text{Find}(X) basically finds the root element of the disjoint set to which X belongs.

The root basically represents a unique ID for a particular disjoint set. (Look at the code for \text{Find}(X))

If we apply \text{Find}(d) or \text{Find}(b) operation for the set in the image below, then it will return '$a$' which is a root element.

Here the thing to note is that, the root element of a root element of any disjoint set is itself i.e., root.parent = root

Algorithm

• Until you reach at the root element, traverse the tree of the disjoint set upwards.

Pseudocode:

FIND(X)
	while x != x.parent
		x = x.parent
		
	return x;

Visualization

---

Quiz Time

Can you find the recursive implementation of the above function?

Answer:

FIND(x)
	if x == x.parent
		return x
	else
		return FIND(x.parent) 

---

Implementation in C++

// Iterative implementation
int Find(x)
{
	while(x != parent[x])
		x = parent[x];
	return x;
}

// Recursive implementation
int Find(x)
{
	if(x == parent[x])
		return x;
	else
		return Find(parent[x]);
}

Time Complexity: This operation can take O(N) in worst case where N is the size of the set-which can be number of total elements at maximum.

This is too much. Right? What else can we do?

We have a technique named "Path compression". The idea of the Path compression is, it re-connects every vertex to the root vertex directly, rather than by a path.

If we apply \text{Find}(d) operation with the path compression, then the following thing will happen.

How can we do it? It is easy, we just need a little modification in \text{Find}(X).

Pseudocode:

FIND(x)
	if x == x.parent
		return x
	else 
		x.parent = FIND(x.parent);
		return x.parent

So every time we run this function, it will re-connect every vertex on the path to the root, directly to the root.

---

Quiz Time

Can you write the iterative version of the above \text{FIND}(X) function with path compression?

Answer:

FIND(x)
	y = x

	while y != y.parent
		y = y.parent
	
	while x != x.parent
		z = x.parent;
		x.parent = y
		x = z
		

---

Implementation in C++

// Iterative Implementation
int Find(x)
{
	int y = x;
	while(y != parent[y])
		y = parent[y];
	
	int parent;
	
	while(x != parent[x])
	{
		parent = parent[x];
		parent[x] = y;
		x = parent;
	}
	
	return x;
}

// Recursive implementation
int Find(x)
{
	if(x == parent[x])
		return x;
	else
		return parent[x] = Find(parent[x]);
}

Time complexity of Find:

1. Without path compression: \mathcal{O}(N)
2. With path compression: \mathcal{O}(\log^*(N))

Note:

• log^*(N) is the iterated logarithm, which is essentially the number of times we have to apply log to N before it becomes less than or equal to 1.
• \mathcal{O}(\log^*(N)) is almost constant time becuase \log^*(N) \leqslant 5 for even such a big number like 2^{65536}.

Operation Union

\text{Union}(X,Y) operation first of all finds root element of both the disjoint sets containing X and Y respectively. Then it connects the root element of one of the disjoint set to the another.

Well, how do we decide which root will connet to which? If we do it randomly then it may increase the tree height up to O(N), which means that the next \text{Find}(x) operation will take O(N) time. Can we do better?

Yes, we have two standard techniques: By size and By rank.

By Size

Union by size technique decides it based on the sizes of the sets. Everytime, the smaller size set is attatched to the larger size set.

Note: The numbers in square bracket represents the size of the set below it.

Pseudocode:

UNION(X,Y)
	Rx = FIND(X), Ry = FIND(Y)

	if Rx == Ry
		return
	if Rx.size > Ry.size
		Ry.parent = Rx
		Rx.size = Rx.size + Ry.size
	else 
		Rx.parent = Ry
		Ry.size = Ry.size + Rx.size

By Rank

In Union by rank technique, shorter tree is attatched to taller tree. Initally rank of each disjoint set is zero.

If both sets have same rank, then the resulting rank will be one greater. Otherwise the resulting rank will be larger of the two.

Note: In the image below, the numbers in square bracket represents the rank of the set below it.

Example 1:

Example 2:

Pseudocode:

UNION(X,Y)
	Rx = FIND(X), Ry = FIND(Y)

	if Rx == Ry
		return
	if Rx.rank > Ry.rank
		Ry.parent = Rx
		if Rx.rank == Ry.rank
			Rx.rank = Rx.rank + 1
	else 
		Rx.parent = Ry
		if Rx.rank == Ry.rank
			Ry.rank = Ry.rank + 1

Implementation in c++

// By size
void union(int x,int y)
{
	int Rx = find(x), Ry = find(y);
	
	if(Rx == Ry)
		return;
		
	if(size[Ry] > size[Rx])
		swap(Rx,Ry);
	
	parent[Ry] = Rx;
	size[Rx] += size[Ry];
		
}

// By Rank
void union(int x,int y)
{
	int Rx = find(x), Ry = find(y);
	
	if(Rx == Ry)
		return;
		
	if(rank[Ry] > rank[Rx])
		swap(Rx,Ry);
	
	parent[Ry] = Rx;
	
	if(rank[Rx] == rank[Ry])
		rank[Rx] += 1;

}

Time Complexity of Union

1. Without path compression(in find): \mathcal{O}(N)
2. With path compression: \mathcal{O}(\log^*(N))

Applications of DSU

1. To keep track of connected components in an undirected graph.
2. In Kruskal's and Boruvka's algorithm to find minimum spanning tree.