Smallest Vertex in the Connected Components of all the Vertices in the Given Undirected Graph

Code

#include <bits/stdc++.h>
using namespace std;
const int M = 3e5 + 7;
//arrays to store parent and size of a set
int parent[M], size[M];
//function used to find the parent of the set in which vertex u is located
int FIND(int u){
   //base case
   if(parent[u] == u)
       return u;
   //recursion + memorization
   return parent[u] = FIND(parent[u]);
}

/*function used to merge two specified sets 
(the set in which vertex u is located and set in which vertex v is located)*/
void UNION(int u, int v){
   //find parent of u and v
   int paru = FIND(u);
   int parv = FIND(v);
   //if u and v belongs to same set
   if(paru == parv)
       return;
   //path compression
   if(size[paru] < size[parv])
       swap(paru, parv);
   
   parent[parv] = paru;
   size[paru] += size[parv];
}
int main(){
   //nodes, edges
   int N, M;
   cin >> N >> M;
   for(int i = 1; i <= N; i++){
       parent[i] = i;
       size[i] = 1;
   }
   for(int i = 0; i < M; ++i){
       int u, v;
       cin >> u >> v;
       //Perform union operation for all the pairs of vertices connected by an edge.
       UNION(u, v);
   }
   /*
   An array that keeps track of the smallest vertex.
   */
   vector <int> minVertex(N + 1, N + 1);
   for(int i = 1; i <= N; i++){
       //if minVertex[ FIND(i) ] > i then set it to i.
       cout << FIND(i) << "\n";
       minVertex[FIND(i)] = min(minVertex[FIND(i)], i);
   }

   for(int i = 1; i <= N; i++){
       //minVertext[ FIND(i) ] is the final answer
       cout << minVertex[FIND(i)] << " ";
   }
   cout << "\n";
   return 0;
}

Dry Run

N    =    8
M    =    4

/*
1 2 3 4 5 6 7 8
*/

For(i = 1 to i = M)
	i = 1, u = 1, v = 2  
		   UNION(1, 2)
	/*
			1 - 2, 3, 4, 5, 6, 7, 8
	*/

	i = 2,  u = 2, v = 7
		   UNION(2, 7)
	/*
			1 - 2 - 7
			4, 5, 6, 7, 8
	*/

	i = 3, u = 8, v = 6
		   UNION(8, 6)
	/*
			1 - 2 - 7
			8 - 6
			4 , 5, 7
	*/  
	i = 4, u = 5, v = 6
	UNION(5, 6)
	/*
			1 - 2 - 7
			8 - 6 - 5
			4 , 7
	*/  

minVertex[] = {9, 9, 9, 9, 9, 9, 9, 9, 9}


For(i = 1 to i = N)
    i = 1, 
       minVertex[FIND(1)] = min(minVertex[FIND(1)], 1) = min(minVertex[1], 1) = min(9, 1) = 1
       minVertex[1] = 1
       // FIND(1) = 1

    i = 2, 
       minVertex[FIND(2)] = min(minVertex[FIND(2)], 2) = min(minVertex[1], 2) = min(1, 2) = 1
       minVertex[1] = 1
       // FIND(2) = 1

    i = 3, 
       minVertex[FIND(3)] = min(minVertex[FIND(3)], 3) = min(minVertex[3], 3) = min(9, 3) = 3
       minVertex[3] = 3
       // FIND(3) = 3 

    i = 4, 
       minVertex[FIND(4)] = min(minVertex[FIND(4)], 4) = min(minVertex[4], 4) = min(9, 4) = 4
       minVertex[4] = 4
       // FIND(4) = 4

    i = 5, 
       minVertex[FIND(5)] = min(minVertex[FIND(5)], 5) = min(minVertex[8], 5) = min(9, 5) = 5
       minVertex[8] = 5
       // FIND(5) = 8

    i = 6, 
       minVertex[FIND(6)] = min(minVertex[FIND(6)], 6) = min(minVertex[8], 6) = min(5, 6) = 5
       minVertex[8] = 5 
      // FIND(6) = 8

    i = 7, 
       minVertex[FIND(7)] = min(minVertex[FIND(7)], 7) = min(minVertex[1], 7) = min(1, 7) = 1
       minVertex[1] = 1
       // FIND(7) = 1

    i = 8, 
       minVertex[FIND(8)] = min(minVertex[FIND(8)], 8) = min(minVertex[8], 8) = min(5, 8) = 5
       minVertex[8] = 8
       // FIND(8) = 8

For(i = 1 to i = N)
   i = 1, minVertex[FIND(1)] = minVertex[1] = 1
   i = 2, minVertex[FIND(2)] = minVertex[1] = 1
   i = 3, minVertex[FIND(3)] = minVertex[3] = 3
   i = 4, minVertex[FIND(4)] = minVertex[4] = 4
   i = 5, minVertex[FIND(5)] = minVertex[8] = 5
   i = 6, minVertex[FIND(5)] = minVertex[8] = 5
   i = 7, minVertex[FIND(7)] = minVertex[1] = 1
   i = 8, minVertex[FIND(8)] = minVertex[8] = 5
   
1, 2, 3, 4, 5, 5, 1, 5 is the final answer

Time Complexity

The time complexity is O(N)

Space Complexity

The space complexity is O(N)

FAQs

1. What is DSU?
   DSU is a data structure that is used to combine two sets efficiently, and it is also able to find the set in which a particular element is located.
    
2. What is more efficient, DSU or DFS?
   For single union or find operation, the worst-case time complexity is O(logN), but if we have many such operations, the average time complexity is O(alpha(N)), where alpha(N) is inverse Ackerman function which makes DSU more efficient then DFS in many cases. But it also depends upon input.

Key Takeaways

In this article, we solved a problem using DSU. If you are doing competitive programming, DSU is one of the most important data structure. Check out this coding ninjas' blog for getting a better hold on it.

Recommended Readings

• Detect cycle in an undirected graph
   

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!