Minimize operations to convert each node of N | 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
N = 3 NEW_LINE adj = [ ] NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT adj . append ( [ ] ) NEW_LINE DEDENT visited = [ ] NEW_LINE ans = 0 NEW_LINE def addEdges ( u , v ) : NEW_LINE INDENT global adj NEW_LINE adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def DFSUtil ( u , foo , foo1 , initial , finall ) : NEW_LINE INDENT global visited , ans , adj NEW_LINE visited [ u ] = True NEW_LINE if ( ( initial [ u - 1 ] ^ foo ) ^ finall [ u - 1 ] == True ) : NEW_LINE INDENT ans += 1 NEW_LINE foo ^= True NEW_LINE DEDENT for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( visited [ adj [ u ] [ i ] ] == False ) : NEW_LINE INDENT DFSUtil ( adj [ u ] [ i ] , foo1 , foo , initial , finall ) NEW_LINE DEDENT DEDENT DEDENT def DFS ( V , initial , finall ) : NEW_LINE INDENT global ans , visited NEW_LINE ans = 0 NEW_LINE visited = [ False ] * V NEW_LINE for u in range ( 1 , 2 ) : NEW_LINE INDENT if ( visited [ u ] == False ) : NEW_LINE INDENT DFSUtil ( u , 0 , 0 , initial , finall ) NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT def countOperations ( N , initial , finall , Edges ) : NEW_LINE INDENT for i in range ( N - 1 ) : NEW_LINE INDENT addEdges ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) NEW_LINE DEDENT DFS ( N + 1 , initial , finall ) NEW_LINE DEDENT Edges = [ [ 1 , 2 ] , [ 1 , 3 ] ] NEW_LINE initial = [ True , True , False ] NEW_LINE finall = [ False , True , True ] NEW_LINE countOperations ( N , initial , finall , Edges ) NEW_LINE