Find if path length is even or odd between given Tree nodes for Q queries | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > adj ( 100000 ) ; vector < int > setNum ( 100000 ) ; void addEdge ( int a1 , int a2 ) { adj [ a1 ] . push_back ( a2 ) ; adj [ a2 ] . push_back ( a1 ) ; } void toBipartite ( int N ) { setNum . assign ( N , -1 ) ; queue < int > q ; q . push ( 0 ) ; setNum [ 0 ] = 0 ; while ( ! q . empty ( ) ) { int v = q . front ( ) ; q . pop ( ) ; for ( int u : adj [ v ] ) { if ( setNum [ u ] == -1 ) { setNum [ u ] = setNum [ v ] ^ 1 ; q . push ( u ) ; } } } } void pathLengthQuery ( int A , int B ) { if ( setNum [ A ] == setNum [ B ] ) { cout << " Odd " << endl ; } else { cout << " Even " << endl ; } } int main ( ) { 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 ) ; return 0 ; }