Minimum number of edges that need to be added to form a triangle | Java implementation of the approach ; Pair class ; Function to return the minimum number of edges that need to be added to the given graph such that it contains at least one triangle ; adj is the adjacency matrix such that adj [ i ] [ j ] = 1 when there is an edge between i and j ; As the graph is undirected so there will be an edge between ( i , j ) and ( j , i ) ; To store the required count of edges ; For every possible vertex triplet ; If the vertices form a triangle ; If no edges are present ; If only 1 edge is required ; Two edges are required ; Driver Code ; Number of nodes ; Storing the edges in a vector of pairs
import java . io . * ; import java . util . * ; class Pair < V , E > { V first ; E second ; Pair ( V first , E second ) { this . first = first ; this . second = second ; } } class GFG { static int minEdges ( Vector < Pair < Integer , Integer > > v , int n ) { int [ ] [ ] adj = new int [ n + 1 ] [ n + 1 ] ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { adj [ v . elementAt ( i ) . first ] [ v . elementAt ( i ) . second ] = 1 ; adj [ v . elementAt ( i ) . second ] [ v . elementAt ( i ) . first ] = 1 ; } int edgesNeeded = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = i + 1 ; j <= n ; j ++ ) { for ( int k = j + 1 ; k <= n ; k ++ ) { if ( adj [ i ] [ j ] == 1 && adj [ j ] [ k ] == 1 && adj [ k ] [ i ] == 1 ) return 0 ; if ( ! ( adj [ i ] [ j ] == 1 adj [ j ] [ k ] == 1 adj [ k ] [ i ] == 1 ) ) edgesNeeded = Math . min ( edgesNeeded , 3 ) ; else { if ( ( adj [ i ] [ j ] == 1 && adj [ j ] [ k ] == 1 ) || ( adj [ j ] [ k ] == 1 && adj [ k ] [ i ] == 1 ) || ( adj [ k ] [ i ] == 1 && adj [ i ] [ j ] == 1 ) ) { edgesNeeded = 1 ; } else edgesNeeded = Math . min ( edgesNeeded , 2 ) ; } } } } return edgesNeeded ; } public static void main ( String [ ] args ) { int n = 3 ; Vector < Pair < Integer , Integer > > v = new Vector < > ( Arrays . asList ( new Pair < > ( 1 , 2 ) , new Pair < > ( 1 , 3 ) ) ) ; System . out . println ( minEdges ( v , n ) ) ; } }