Minimize operations to convert each node of N | Java program for the above approach ; Create adjacency list ; Function to add an edges in graph ; Function to perform the DFS of graph recursively from a given vertex u ; Check for the condition for the flipping of node 's initial value ; Traverse all the children of the current source node u ; Swap foo and foo1 signifies there is change of level ; Function to perform the DFSUtil ( ) for all the unvisited vertices ; Traverse the given set of nodes ; If the current node is unvisited ; Print the number of operations ; Function to count the number of flips required to change initial node values to final node value ; Add the given edges ; DFS Traversal ; Driver code
import java . util . * ; public class Main { static int N = 3 ; static Vector < Vector < Integer > > adj = new Vector < Vector < Integer > > ( ) ; static Vector < Boolean > visited ; static int ans ; static void addEdges ( int u , int v ) { adj . get ( u ) . add ( v ) ; adj . get ( v ) . add ( u ) ; } static void DFSUtil ( int u , boolean foo , boolean foo1 , boolean [ ] initial , boolean [ ] finall ) { visited . set ( u , true ) ; if ( ( initial [ u - 1 ] ^ foo ) ^ finall [ u - 1 ] == true ) { ans += 1 ; foo ^= true ; } for ( int i = 0 ; i < adj . get ( u ) . size ( ) ; i ++ ) { if ( visited . get ( adj . get ( u ) . get ( i ) ) == false ) DFSUtil ( adj . get ( u ) . get ( i ) , foo1 , foo , initial , finall ) ; } } static void DFS ( int V , boolean [ ] initial , boolean [ ] finall ) { ans = 0 ; visited = new Vector < Boolean > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { visited . add ( false ) ; } for ( int u = 1 ; u <= 1 ; u ++ ) { if ( visited . get ( u ) == false ) DFSUtil ( u , false , false , initial , finall ) ; } System . out . print ( ans ) ; } static void countOperations ( int N , boolean [ ] initial , boolean [ ] finall , int [ ] [ ] Edges ) { for ( int i = 0 ; i < N - 1 ; i ++ ) { addEdges ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } DFS ( N + 1 , initial , finall ) ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < N + 1 ; i ++ ) { adj . add ( new Vector < Integer > ( ) ) ; } int [ ] [ ] Edges = { { 1 , 2 } , { 1 , 3 } } ; boolean [ ] initial = { true , true , false } ; boolean [ ] finall = { false , true , true } ; countOperations ( N , initial , finall , Edges ) ; } }