Longest path between any pair of vertices | C ++ program to find the longest cable length between any two cities . ; visited [ ] array to make nodes visited src is starting node for DFS traversal prev_len is sum of cable length till current node max_len is pointer which stores the maximum length of cable value after DFS traversal ; Mark the src node visited ; curr_len is for length of cable from src city to its adjacent city ; Adjacent is pair type which stores destination city and cable length ; Traverse all adjacent ; Adjacent element ; If node or city is not visited ; Total length of cable from src city to its adjacent ; Call DFS for adjacent city ; If total cable length till now greater than previous length then update it ; make curr_len = 0 for next adjacent ; n is number of cities or nodes in graph cable_lines is total cable_lines among the cities or edges in graph ; maximum length of cable among the connected cities ; call DFS for each city to find maximum length of cable ; initialize visited array with 0 ; Call DFS for src vertex i ; driver program to test the input ; n is number of cities ; create undirected graph first edge ; second edge ; third edge ; fourth edge ; fifth edge
#include <bits/stdc++.h> NEW_LINE using namespace std ; void DFS ( vector < pair < int , int > > graph [ ] , int src , int prev_len , int * max_len , vector < bool > & visited ) { visited [ src ] = 1 ; int curr_len = 0 ; pair < int , int > adjacent ; for ( int i = 0 ; i < graph [ src ] . size ( ) ; i ++ ) { adjacent = graph [ src ] [ i ] ; if ( ! visited [ adjacent . first ] ) { curr_len = prev_len + adjacent . second ; DFS ( graph , adjacent . first , curr_len , max_len , visited ) ; } if ( ( * max_len ) < curr_len ) * max_len = curr_len ; curr_len = 0 ; } } int longestCable ( vector < pair < int , int > > graph [ ] , int n ) { int max_len = INT_MIN ; for ( int i = 1 ; i <= n ; i ++ ) { vector < bool > visited ( n + 1 , false ) ; DFS ( graph , i , 0 , & max_len , visited ) ; } return max_len ; } int main ( ) { int n = 6 ; vector < pair < int , int > > graph [ n + 1 ] ; graph [ 1 ] . push_back ( make_pair ( 2 , 3 ) ) ; graph [ 2 ] . push_back ( make_pair ( 1 , 3 ) ) ; graph [ 2 ] . push_back ( make_pair ( 3 , 4 ) ) ; graph [ 3 ] . push_back ( make_pair ( 2 , 4 ) ) ; graph [ 2 ] . push_back ( make_pair ( 6 , 2 ) ) ; graph [ 6 ] . push_back ( make_pair ( 2 , 2 ) ) ; graph [ 4 ] . push_back ( make_pair ( 6 , 6 ) ) ; graph [ 6 ] . push_back ( make_pair ( 4 , 6 ) ) ; graph [ 5 ] . push_back ( make_pair ( 6 , 5 ) ) ; graph [ 6 ] . push_back ( make_pair ( 5 , 5 ) ) ; cout << " Maximum ▁ length ▁ of ▁ cable ▁ = ▁ " << longestCable ( graph , n ) ; return 0 ; }