Minimum number of edges that need to be added to form a triangle | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minEdges ( vector < pair < int , int > > v , int n ) { vector < vector < int > > adj ; adj . resize ( n + 1 ) ; for ( int i = 0 ; i < adj . size ( ) ; i ++ ) adj [ i ] . resize ( n + 1 , 0 ) ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { adj [ v [ i ] . first ] [ v [ i ] . second ] = 1 ; adj [ v [ i ] . second ] [ v [ i ] . first ] = 1 ; } int edgesNeeded = 3 ; 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 ] && adj [ j ] [ k ] && adj [ k ] [ i ] ) return 0 ; if ( ! ( adj [ i ] [ j ] adj [ j ] [ k ] adj [ k ] [ i ] ) ) edgesNeeded = min ( edgesNeeded , 3 ) ; else { if ( ( adj [ i ] [ j ] && adj [ j ] [ k ] ) || ( adj [ j ] [ k ] && adj [ k ] [ i ] ) || ( adj [ k ] [ i ] && adj [ i ] [ j ] ) ) { edgesNeeded = 1 ; } else edgesNeeded = min ( edgesNeeded , 2 ) ; } } } } return edgesNeeded ; } int main ( ) { int n = 3 ; vector < pair < int , int > > v = { { 1 , 2 } , { 1 , 3 } } ; cout << minEdges ( v , n ) ; return 0 ; }