Smallest vertex in the connected components of all the vertices in given undirect graph | C ++ program for the above approach ; Stores the parent and size of the set of the ith element ; Function to initialize the ith set ; Function to find set of ith vertex ; Base Case ; Recursive call to find set ; Function to unite the set that includes a and the set that includes b ; If a and b are not from same set ; Function to find the smallest vertex in the connected component of the ith vertex for all i in range [ 1 , N ] ; Loop to initialize the ith set ; Loop to unite all vertices connected by edges into the same set ; Stores the minimum vertex value for ith set ; Loop to iterate over all vertices ; If current vertex does not exist in minVal initialize it with i ; Update the minimum value of the set having the ith vertex ; Loop to print required answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int maxn = 100 ; int parent [ maxn ] , Size [ maxn ] ; void make_set ( int v ) { parent [ v ] = v ; Size [ v ] = 1 ; } int find_set ( int v ) { if ( v == parent [ v ] ) { return v ; } return parent [ v ] = find_set ( parent [ v ] ) ; } void union_sets ( int a , int b ) { a = find_set ( a ) ; b = find_set ( b ) ; if ( a != b ) { if ( Size [ a ] < Size [ b ] ) swap ( a , b ) ; parent [ b ] = a ; Size [ a ] += Size [ b ] ; } } void findMinVertex ( int N , vector < pair < int , int > > edges ) { for ( int i = 1 ; i <= N ; i ++ ) { make_set ( i ) ; } for ( int i = 0 ; i < edges . size ( ) ; i ++ ) { union_sets ( edges [ i ] . first , edges [ i ] . second ) ; } unordered_map < int , int > minVal ; for ( int i = 1 ; i <= N ; i ++ ) { if ( minVal [ find_set ( i ) ] == 0 ) { minVal [ find_set ( i ) ] = i ; } else { minVal [ find_set ( i ) ] = min ( minVal [ find_set ( i ) ] , i ) ; } } for ( int i = 1 ; i <= N ; i ++ ) { cout << minVal [ find_set ( i ) ] << " ▁ " ; } } int main ( ) { int N = 6 ; vector < pair < int , int > > edges = { { 1 , 3 } , { 2 , 4 } } ; findMinVertex ( N , edges ) ; return 0 ; }