Minimum Bipartite Groups | ''Function to find the height sizeof the current component with vertex s ; Visit the current Node ; Call DFS recursively to find the maximum height of current CC ; If the node is not visited then the height recursively for next element ; Function to find the minimum Groups ; Initialise with visited array ; To find the minimum groups ; Traverse all the non visited Node and calculate the height of the tree with current node as a head ; If the current is not visited therefore , we get another CC ; Return the minimum bipartite matching ; Function that adds the current edges in the given graph ; Driver code ; Adjacency List ; Adding edges to List
import sys NEW_LINE def height ( s , adj , visited ) : NEW_LINE INDENT visited [ s ] = 1 NEW_LINE h = 0 NEW_LINE for child in adj [ s ] : NEW_LINE INDENT if ( visited [ child ] == 0 ) : NEW_LINE INDENT h = max ( h , 1 + height ( child , adj , visited ) ) NEW_LINE DEDENT DEDENT return h NEW_LINE DEDENT def minimumGroups ( adj , N ) : NEW_LINE INDENT visited = [ 0 for i in range ( N + 1 ) ] NEW_LINE groups = - sys . maxsize NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( visited [ i ] == 0 ) : NEW_LINE INDENT comHeight = height ( i , adj , visited ) NEW_LINE groups = max ( groups , comHeight ) NEW_LINE DEDENT DEDENT return groups NEW_LINE DEDENT def addEdge ( adj , u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 5 NEW_LINE adj = [ [ ] for i in range ( N + 1 ) ] NEW_LINE addEdge ( adj , 1 , 2 ) NEW_LINE addEdge ( adj , 3 , 2 ) NEW_LINE addEdge ( adj , 4 , 3 ) NEW_LINE print ( minimumGroups ( adj , N ) ) NEW_LINE DEDENT