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 ; Drivers Code ; Adjacency List ; Adding edges to List
#include <bits/stdc++.h> NEW_LINE using namespace std ; int height ( int s , vector < int > adj [ ] , int * visited ) { visited [ s ] = 1 ; int h = 0 ; for ( auto & child : adj [ s ] ) { if ( visited [ child ] == 0 ) { h = max ( h , 1 + height ( child , adj , visited ) ) ; } } return h ; } int minimumGroups ( vector < int > adj [ ] , int N ) { int visited [ N + 1 ] = { 0 } ; int groups = INT_MIN ; for ( int i = 1 ; i <= N ; i ++ ) { if ( visited [ i ] == 0 ) { int comHeight ; comHeight = height ( i , adj , visited ) ; groups = max ( groups , comHeight ) ; } } return groups ; } void addEdge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } int main ( ) { int N = 5 ; vector < int > adj [ N + 1 ] ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 3 , 2 ) ; addEdge ( adj , 4 , 3 ) ; cout << minimumGroups ( adj , N ) ; }