Maximum number of edges to be added to a tree so that it stays a Bipartite graph | C # code to print maximum edges such that Tree remains a Bipartite graph ; To store counts of nodes with two colors ; Increment count of nodes with current color ; Traversing adjacent nodes ; Not recurring for the parent node ; Finds maximum number of edges that can be added without violating Bipartite property . ; Do a DFS to count number of nodes of each color ; Driver code
using System ; using System . Collections . Generic ; class GFG { static long [ ] count_color = new long [ 2 ] ; static void dfs ( List < int > [ ] adj , int node , int parent , bool color ) { count_color [ color == false ? 0 : 1 ] ++ ; for ( int i = 0 ; i < adj [ node ] . Count ; i ++ ) { if ( adj [ node ] [ i ] != parent ) dfs ( adj , adj [ node ] [ i ] , node , ! color ) ; } } static int findMaxEdges ( List < int > [ ] adj , int n ) { dfs ( adj , 1 , 0 , false ) ; return ( int ) ( count_color [ 0 ] * count_color [ 1 ] - ( n - 1 ) ) ; } public static void Main ( String [ ] args ) { int n = 5 ; List < int > [ ] adj = new List < int > [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) adj [ i ] = new List < int > ( ) ; adj [ 1 ] . Add ( 2 ) ; adj [ 1 ] . Add ( 3 ) ; adj [ 2 ] . Add ( 4 ) ; adj [ 3 ] . Add ( 5 ) ; Console . WriteLine ( findMaxEdges ( adj , n ) ) ; } }