Minimum number of edges that need to be added to form a triangle | C # 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
using System ; using System . Collections . Generic ; class Pair { public int first ; public int second ; public Pair ( int first , int second ) { this . first = first ; this . second = second ; } } class GFG { static int minEdges ( List < Pair > v , int n ) { int [ , ] adj = new int [ n + 1 , n + 1 ] ; for ( int i = 0 ; i < v . Count ; i ++ ) { adj [ v [ i ] . first , v [ i ] . second ] = 1 ; adj [ v [ i ] . second , v [ 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 ; List < Pair > v = new List < Pair > ( ) ; v . Add ( new Pair ( 1 , 2 ) ) ; v . Add ( new Pair ( 1 , 3 ) ) ; Console . WriteLine ( minEdges ( v , n ) ) ; } }