Find if path length is even or odd between given Tree nodes for Q queries | Python program for the above approach ; Stores the input tree ; Stores the set number of all nodes ; Function to add an edge in the tree ; Function to convert the given tree into a bipartite graph using BFS ; Set the set number to - 1 for all node of the given tree ; Stores the current node during the BFS traversal of the tree ; Initialize the set number of 1 st node and enqueue it ; BFS traversal of the given tree ; Current node ; Traverse over all neighbours of the current node ; If the set is not assigned ; Assign set number to node u ; Function to find if the path length between node A and B is even or odd ; If the set number of both nodes is same , path length is odd else even ; Driver Code ; Function to convert tree into bipartite
from queue import Queue NEW_LINE adj = [ [ 0 ] * 100000 ] * 100000 NEW_LINE setNum = [ 0 ] * 100000 NEW_LINE def addEdge ( a1 , a2 ) : NEW_LINE INDENT adj [ a1 ] . append ( a2 ) ; NEW_LINE adj [ a2 ] . append ( a1 ) ; NEW_LINE DEDENT def toBipartite ( N ) : NEW_LINE INDENT for i in range ( 0 , N ) : NEW_LINE INDENT setNum [ i ] = - 1 NEW_LINE DEDENT q = Queue ( ) ; NEW_LINE q . put ( 0 ) ; NEW_LINE setNum [ 0 ] = 0 ; NEW_LINE while ( not q . empty ( ) ) : NEW_LINE INDENT v = q . queue [ 0 ] ; NEW_LINE q . get ( ) ; NEW_LINE for u in adj [ v ] : NEW_LINE INDENT if ( setNum [ u ] == - 1 ) : NEW_LINE INDENT setNum [ u ] = setNum [ v ] ^ 1 ; NEW_LINE q . put ( u ) ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def pathLengthQuery ( A , B ) : NEW_LINE INDENT if ( setNum [ A ] == setNum [ B ] ) : NEW_LINE INDENT print ( " Odd " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Even " ) ; NEW_LINE DEDENT DEDENT N = 7 ; NEW_LINE addEdge ( 0 , 1 ) ; NEW_LINE addEdge ( 0 , 2 ) ; NEW_LINE addEdge ( 1 , 3 ) ; NEW_LINE addEdge ( 3 , 4 ) ; NEW_LINE addEdge ( 3 , 5 ) ; NEW_LINE addEdge ( 2 , 6 ) ; NEW_LINE toBipartite ( N ) ; NEW_LINE pathLengthQuery ( 4 , 2 ) ; NEW_LINE pathLengthQuery ( 0 , 4 ) ; NEW_LINE