Find Maximum Shortest Distance in Each Component of a Graph | C ++ program for the above approach ; Below dfs function will be used to get the connected components of a graph and stores all the connected nodes in the vector component ; Mark this vertex as visited ; Put this node in component vector ; For all other vertices in graph ; If there is an edge between src and dest i . e . , the value of graph [ u ] [ v ] != INT_MAX ; If we haven 't visited dest  then recursively apply  dfs on dest ; Below is the Floyd Warshall Algorithm which is based on Dynamic Programming ; For every vertex of graph find the shortest distance with other vertices ; Taking care of interger overflow ; Update distance between vertex i and j if choosing k as an intermediate vertex make a shorter distance ; Function to find the maximum shortest path distance in a component by checking the shortest distances between all possible pairs of nodes ; If the maxDistance is still INT_MIN then return 0 because this component has a single element ; Below function uses above two method to get the maximum shortest distances in each component of the graph the function returns a vector , where each element denotes maximum shortest path distance for a component ; Find the connected components ; For storing the nodes in a particular component ; Now for each unvisited node run the dfs to get the connected component having this unvisited node ; First of all clear the temp ; Now for all - pair find the shortest path distances using Floyd Warshall ; Now for each component find the maximum shortest distance and store it in result ; Driver Code ; Adjacency Matrix for the first graph in the examples ; Find the maximum shortest distances ; Printing the maximum shortest path distances for each components
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int src , vector < bool > & visited , vector < vector < int > > & graph , vector < int > & component , int N ) { visited [ src ] = true ; component . push_back ( src ) ; for ( int dest = 0 ; dest < N ; dest ++ ) { if ( graph [ src ] [ dest ] != INT_MAX ) { if ( ! visited [ dest ] ) dfs ( dest , visited , graph , component , N ) ; } } } void floydWarshall ( vector < vector < int > > & graph , int N ) { for ( int k = 0 ; k < N ; k ++ ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( graph [ i ] [ k ] != INT_MAX && graph [ k ] [ j ] != INT_MAX ) { if ( graph [ i ] [ k ] + graph [ k ] [ j ] < graph [ i ] [ j ] ) graph [ i ] [ j ] = graph [ i ] [ k ] + graph [ k ] [ j ] ; } } } } } int maxInThisComponent ( vector < int > & component , vector < vector < int > > & graph ) { int maxDistance = INT_MIN ; int n = component . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { maxDistance = max ( maxDistance , graph [ component [ i ] ] [ component [ j ] ] ) ; } } return ( maxDistance == INT_MIN ? 0 : maxDistance ) ; } vector < int > maximumShortesDistances ( vector < vector < int > > & graph , int N ) { vector < bool > visited ( N , false ) ; vector < vector < int > > components ; vector < int > temp ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { temp . clear ( ) ; dfs ( i , visited , graph , temp , N ) ; components . push_back ( temp ) ; } } floydWarshall ( graph , N ) ; vector < int > result ; int numOfComp = components . size ( ) ; int maxDistance ; for ( int i = 0 ; i < numOfComp ; i ++ ) { maxDistance = maxInThisComponent ( components [ i ] , graph ) ; result . push_back ( maxDistance ) ; } return result ; } int main ( ) { int N = 8 ; const int inf = INT_MAX ; vector < vector < int > > graph1 = { { 0 , inf , 9 , inf , inf , inf , 3 , inf } , { inf , 0 , inf , 10 , 1 , 8 , inf , inf } , { 9 , inf , 0 , inf , inf , inf , 11 , inf } , { inf , 10 , inf , 0 , 5 , 13 , inf , inf } , { inf , 1 , inf , 5 , 0 , 3 , inf , inf } , { 8 , inf , inf , 13 , 3 , 0 , inf , inf } , { 3 , inf , 11 , inf , inf , inf , 0 , inf } , { inf , inf , inf , inf , inf , inf , inf , 0 } , } ; vector < int > result1 = maximumShortesDistances ( graph1 , N ) ; for ( int mx1 : result1 ) cout << mx1 << ' ▁ ' ; return 0 ; }