Minimum steps to color the tree with given colors | C ++ implementation of the approach ; To store the required answer ; To store the graph ; Function to add edges ; Dfs function ; When there is difference in colors ; For all it 's child nodes ; Driver code ; Here zero is for parent of node 1 ; Adding edges in the graph ; Dfs call ; Required answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ans = 0 ; vector < int > gr [ 100005 ] ; void Add_Edge ( int u , int v ) { gr [ u ] . push_back ( v ) ; gr [ v ] . push_back ( u ) ; } void dfs ( int child , int par , int color [ ] ) { if ( color [ child ] != color [ par ] ) ans ++ ; for ( auto it : gr [ child ] ) { if ( it == par ) continue ; dfs ( it , child , color ) ; } } int main ( ) { int color [ ] = { 0 , 1 , 2 , 3 , 2 , 2 , 3 } ; Add_Edge ( 1 , 2 ) ; Add_Edge ( 1 , 3 ) ; Add_Edge ( 2 , 4 ) ; Add_Edge ( 2 , 5 ) ; Add_Edge ( 3 , 6 ) ; dfs ( 1 , 0 , color ) ; cout << ans ; return 0 ; }