Maximum number of edges to be added to a tree so that it stays 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 To store counts of nodes with two colors
def dfs ( adj , node , parent , color ) : NEW_LINE INDENT count_color [ color ] += 1 NEW_LINE for i in range ( len ( adj [ node ] ) ) : NEW_LINE INDENT if ( adj [ node ] [ i ] != parent ) : NEW_LINE INDENT dfs ( adj , adj [ node ] [ i ] , node , not color ) NEW_LINE DEDENT DEDENT DEDENT def findMaxEdges ( adj , n ) : NEW_LINE INDENT dfs ( adj , 1 , 0 , 0 ) NEW_LINE return ( count_color [ 0 ] * count_color [ 1 ] - ( n - 1 ) ) NEW_LINE DEDENT count_color = [ 0 , 0 ] NEW_LINE n = 5 NEW_LINE adj = [ [ ] for i in range ( n + 1 ) ] NEW_LINE adj [ 1 ] . append ( 2 ) NEW_LINE adj [ 1 ] . append ( 3 ) NEW_LINE adj [ 2 ] . append ( 4 ) NEW_LINE adj [ 3 ] . append ( 5 ) NEW_LINE print ( findMaxEdges ( adj , n ) ) NEW_LINE