Find if path length is even or odd between given Tree nodes for Q queries | Java 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
import java . io . * ; import java . util . * ; class GFG { @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] adj = new Vector [ 100000 ] ; static Vector < Integer > setNum = new Vector < Integer > ( 100000 ) ; static void addEdge ( int a1 , int a2 ) { adj [ a1 ] . add ( a2 ) ; adj [ a2 ] . add ( a1 ) ; } static void toBipartite ( int N ) { for ( int i = 0 ; i < 100000 ; i ++ ) setNum . add ( - 1 ) ; Queue < Integer > q = new LinkedList < > ( ) ; q . add ( 0 ) ; setNum . set ( 0 , 0 ) ; while ( ! q . isEmpty ( ) ) { int v = q . peek ( ) ; q . remove ( ) ; for ( int u : adj [ v ] ) { if ( setNum . get ( u ) == - 1 ) { setNum . set ( u , setNum . get ( v ) ^ 1 ) ; q . add ( u ) ; } } } } static void pathLengthQuery ( int A , int B ) { if ( setNum . get ( A ) == setNum . get ( B ) ) { System . out . println ( " Odd " ) ; } else { System . out . println ( " Even " ) ; } } public static void main ( String [ ] args ) { for ( int i = 0 ; i < 100000 ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; int N = 7 ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 3 , 4 ) ; addEdge ( 3 , 5 ) ; addEdge ( 2 , 6 ) ; toBipartite ( N ) ; pathLengthQuery ( 4 , 2 ) ; pathLengthQuery ( 0 , 4 ) ; } }