Find maximum matching in a given Binary Tree | Python3 program for the above approach ; Adjacency list to store edges ; Add an edge between U and V in tree ; Edge from u to v ; Edge from V to U ; Function that finds the maximum matching of the DFS ; Go further as we are not allowed to go towards its parent ; If U and its parent P is not taken then we must take & mark them as taken ; Increment size of edge set ; Function to find the maximum matching in a graph ; Taking 1 as a root of the tree ; Print maximum Matching ; Driver Code ; Joining edge between two nodes in tree ; Function Call
N = 10000 NEW_LINE adj = { } NEW_LINE used = [ 0 for i in range ( N ) ] NEW_LINE max_matching = 0 NEW_LINE def AddEdge ( u , v ) : NEW_LINE INDENT if u not in adj : NEW_LINE INDENT adj [ u ] = [ ] NEW_LINE DEDENT if v not in adj : NEW_LINE INDENT adj [ v ] = [ ] NEW_LINE DEDENT adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def Matching_dfs ( u , p ) : NEW_LINE INDENT global max_matching NEW_LINE for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( adj [ u ] [ i ] != p ) : NEW_LINE INDENT Matching_dfs ( adj [ u ] [ i ] , u ) NEW_LINE DEDENT DEDENT if ( not used [ u ] and not used [ p ] and p != 0 ) : NEW_LINE INDENT max_matching += 1 NEW_LINE used [ u ] = 1 NEW_LINE used [ p ] = 1 NEW_LINE DEDENT DEDENT def maxMatching ( ) : NEW_LINE INDENT Matching_dfs ( 1 , 0 ) NEW_LINE print ( max_matching ) NEW_LINE DEDENT n = 5 NEW_LINE AddEdge ( 1 , 2 ) NEW_LINE AddEdge ( 1 , 3 ) NEW_LINE AddEdge ( 3 , 4 ) NEW_LINE AddEdge ( 3 , 5 ) NEW_LINE maxMatching ( ) NEW_LINE