Construct a graph using N vertices whose shortest distance between K pair of vertices is 2 | C ++ program to implement the above approach ; Function to construct the simple and connected graph such that the distance between exactly K pairs of vertices is 2 ; Stores maximum possible count of edges in a graph ; Base Case ; Stores edges of a graph ; Connect all vertices of pairs ( i , j ) ; Print first ( ( N - 1 ) + Max - K ) elements of edges [ ] ; Driver Code
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; void constGraphWithCon ( int N , int K ) { int Max = ( ( N - 1 ) * ( N - 2 ) ) / 2 ; if ( K > Max ) { cout << -1 << endl ; return ; } vector < pair < int , int > > ans ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = i + 1 ; j <= N ; j ++ ) { ans . emplace_back ( make_pair ( i , j ) ) ; } } for ( int i = 0 ; i < ( N - 1 ) + Max - K ; i ++ ) { cout << ans [ i ] . first << " ▁ " << ans [ i ] . second << endl ; } } int main ( ) { int N = 5 , K = 3 ; constGraphWithCon ( N , K ) ; return 0 ; }