text: Find maximum matching in a given Binary Tree | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  10000 NEW_LINE vector < int > adj [ N ] ; int used [ N ] ; int max_matching ; void AddEdge ( int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } void Matching_dfs ( int u , int p ) { for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( adj [ u ] [ i ] != p ) { Matching_dfs ( adj [ u ] [ i ] , u ) ; } } if ( ! used [ u ] and ! used [ p ] and p != 0 ) { max_matching ++ ; used [ u ] = used [ p ] = 1 ; } } void maxMatching ( ) { Matching_dfs ( 1 , 0 ) ; cout << max_matching << " STRNEWLINE " ; } int main ( ) { int n = 5 ; AddEdge ( 1 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 3 , 4 ) ; AddEdge ( 3 , 5 ) ; maxMatching ( ) ; return 0 ; }