Find maximum matching in a given Binary Tree | Java 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
import java . util . * ; class GFG { static final int N = 10000 ; @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] adj = new Vector [ N ] ; static int used [ ] = new int [ N ] ; static int max_matching ; static void AddEdge ( int u , int v ) { adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } static void Matching_dfs ( int u , int p ) { for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( adj [ u ] . get ( i ) != p ) { Matching_dfs ( adj [ u ] . get ( i ) , u ) ; } } if ( used [ u ] == 0 && used [ p ] == 0 && p != 0 ) { max_matching ++ ; used [ u ] = used [ p ] = 1 ; } } static void maxMatching ( ) { Matching_dfs ( 1 , 0 ) ; System . out . print ( max_matching + "NEW_LINE"); } public static void main ( String [ ] args ) { for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; AddEdge ( 1 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 3 , 4 ) ; AddEdge ( 3 , 5 ) ; maxMatching ( ) ; } }