Construct a graph using N vertices whose shortest distance between K pair of vertices is 2 | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void constGraphWithCon ( int N , int K ) { int Max = ( ( N - 1 ) * ( N - 2 ) ) / 2 ; if ( K > Max ) { System . out . print ( - 1 + "NEW_LINE"); return ; } Vector < pair > ans = new Vector < > ( ) ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = i + 1 ; j <= N ; j ++ ) { ans . add ( new pair ( i , j ) ) ; } } for ( int i = 0 ; i < ( N - 1 ) + Max - K ; i ++ ) { System . out . print ( ans . get ( i ) . first + " ▁ " + ans . get ( i ) . second + "NEW_LINE"); } } public static void main ( String [ ] args ) { int N = 5 , K = 3 ; constGraphWithCon ( N , K ) ; } }