Given a generic tree consisting of N nodes and (N – 1) edges and an array of queries query[] of size Q consisting of the type {A, B}, the task for each query is to check whether the path length between two given nodes A and B is even or odd.
Examples:
Input: query[] = {{2, 4}, {4, 0}}
Output:
Odd
Even
Explanation:
For the 1st query A = 2 and B = 4. The path from A to B is 2 -> 0 -> 1 -> 3 -> 4 having a length of 5 i.e., Odd.
For the 2nd query A = 4 and B = 0. The path from A to B is 4 -> 3 -> 1 -> 0 having a length of 4 i.e., Even.
Approach: The given problem can be efficiently solved by converting the tree into a Bipartite Graph. It can be observed that if the given nodes A and B in a query are on the same side in the constructed bipartite graph, then the path length between A and B must be odd and if A and B are on different sides, then the path length must be odd. Below are the steps to follow:
- Traverse the given tree using the BFS Traversal.
- Divide all nodes into 2 sets such that all the two adjacent nodes in the tree are in different sets (i.e., 0 or 1). In order to do so, assign an alternating set number to each level during the BFS traversal by assigning the set number of current nodes = 1 XOR the number of the parent of the current node.
- After completing the above steps, traverse the given array of queries query[] and if the set number of both the nodes are the same, the path length of A to B is Odd. Otherwise, it is Even.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the input treevector<vector<int> > adj(100000);// Stores the set number of all nodesvector<int> setNum(100000);// Function to add an edge in the treevoid addEdge(int a1, int a2){ adj[a1].push_back(a2); adj[a2].push_back(a1);}// Function to convert the given tree// into a bipartite graph using BFSvoid toBipartite(int N){ // Set the set number to -1 for // all node of the given tree setNum.assign(N, -1); // Stores the current node during // the BFS traversal of the tree queue<int> q; // Initialize the set number of // 1st node and enqueue it q.push(0); setNum[0] = 0; // BFS traversal of the given tree while (!q.empty()) { // Current node int v = q.front(); q.pop(); // Traverse over all neighbours // of the current node for (int u : adj[v]) { // If the set is not assigned if (setNum[u] == -1) { // Assign set number to node u setNum[u] = setNum[v] ^ 1; q.push(u); } } }}// Function to find if the path length// between node A and B is even or oddvoid pathLengthQuery(int A, int B){ // If the set number of both nodes is // same, path length is odd else even if (setNum[A] == setNum[B]) { cout << "Odd" << endl; } else { cout << "Even" << endl; }}// Driver Codeint main(){ int N = 7; addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(3, 4); addEdge(3, 5); addEdge(2, 6); // Function to convert tree into // bipartite toBipartite(N); pathLengthQuery(4, 2); pathLengthQuery(0, 4); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Stores the input tree@SuppressWarnings("unchecked")static Vector<Integer> []adj = new Vector[100000];// Stores the set number of all nodesstatic Vector<Integer> setNum = new Vector<Integer>(100000);// Function to add an edge in the treestatic void addEdge(int a1, int a2){ adj[a1].add(a2); adj[a2].add(a1);}// Function to convert the given tree// into a bipartite graph using BFSstatic void toBipartite(int N){ // Set the set number to -1 for // all node of the given tree for (int i = 0; i < 100000; i++) setNum.add(-1); // Stores the current node during // the BFS traversal of the tree Queue<Integer> q = new LinkedList<>(); // Initialize the set number of // 1st node and enqueue it q.add(0); setNum.set(0, 0); // BFS traversal of the given tree while (!q.isEmpty()) { // Current node int v = q.peek(); q.remove(); // Traverse over all neighbours // of the current node for (int u : adj[v]) { // If the set is not assigned if (setNum.get(u) == -1) { // Assign set number to node u setNum.set(u, setNum.get(v) ^ 1); q.add(u); } } }}// Function to find if the path length// between node A and B is even or oddstatic void pathLengthQuery(int A, int B){ // If the set number of both nodes is // same, path length is odd else even if (setNum.get(A) == setNum.get(B)) { System.out.println("Odd"); } else { System.out.println("Even"); }}// Driver Codepublic 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); // Function to convert tree into // bipartite toBipartite(N); pathLengthQuery(4, 2); pathLengthQuery(0, 4);}}// This code is contributed by Dharanendra L V. |
Python3
# Python program for the above approachfrom queue import Queue # Stores the input treeadj = [[0] * 100000] * 100000# Stores the set number of all nodessetNum = [0] * 100000# Function to add an edge in the treedef addEdge(a1, a2): adj[a1].append(a2); adj[a2].append(a1);# Function to convert the given tree# into a bipartite graph using BFSdef toBipartite(N): # Set the set number to -1 for # all node of the given tree for i in range(0, N): setNum[i] = -1 # Stores the current node during # the BFS traversal of the tree q = Queue(); # Initialize the set number of # 1st node and enqueue it q.put(0); setNum[0] = 0; # BFS traversal of the given tree while (not q.empty()): # Current node v = q.queue[0]; q.get(); # Traverse over all neighbours # of the current node for u in adj[v]: # If the set is not assigned if (setNum[u] == -1): # Assign set number to node u setNum[u] = setNum[v] ^ 1; q.put(u); # Function to find if the path length# between node A and B is even or odddef pathLengthQuery(A, B): # If the set number of both nodes is # same, path length is odd else even if (setNum[A] == setNum[B]): print("Odd"); else: print("Even");# Driver CodeN = 7;addEdge(0, 1);addEdge(0, 2);addEdge(1, 3);addEdge(3, 4);addEdge(3, 5);addEdge(2, 6); # Function to convert tree into # bipartitetoBipartite(N);pathLengthQuery(4, 2);pathLengthQuery(0, 4);# This code is contributed by _saurabh_jaiswal. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Stores the input treestatic List<int> []adj = new List<int>[100000];// Stores the set number of all nodesstatic List<int> setNum = new List<int>(100000);// Function to add an edge in the treestatic void addEdge(int a1, int a2){ adj[a1].Add(a2); adj[a2].Add(a1);}// Function to convert the given tree// into a bipartite graph using BFSstatic void toBipartite(int N){ // Set the set number to -1 for // all node of the given tree for (int i = 0; i < 100000; i++) setNum.Add(-1); // Stores the current node during // the BFS traversal of the tree Queue<int> q = new Queue<int>(); // Initialize the set number of // 1st node and enqueue it q.Enqueue(0); setNum[0] = 0; // BFS traversal of the given tree while (q.Count!=0) { // Current node int v = q.Peek(); q.Dequeue(); // Traverse over all neighbours // of the current node foreach (int u in adj[v]) { // If the set is not assigned if (setNum[u] == -1) { // Assign set number to node u setNum[u] = ( setNum[v] ^ 1); q.Enqueue(u); } } }}// Function to find if the path length// between node A and B is even or oddstatic void pathLengthQuery(int A, int B){ // If the set number of both nodes is // same, path length is odd else even if (setNum[A] == setNum[B]) { Console.WriteLine("Odd"); } else { Console.WriteLine("Even"); }}// Driver Codepublic static void Main(String[] args) { for (int i = 0; i < 100000; i++) adj[i] = new List<int>(); int N = 7; addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(3, 4); addEdge(3, 5); addEdge(2, 6); // Function to convert tree into // bipartite toBipartite(N); pathLengthQuery(4, 2); pathLengthQuery(0, 4);}}// This code is contributed by shikhasingrajput |
Javascript
<script> //JavaScript code for the above approach // Stores the input tree let adj = Array(100000).fill().map(() => []); // Stores the set number of all nodes let setNum = Array(100000).fill(-1); // Function to add an edge in the tree function addEdge(a1, a2) { adj[a1].push(a2); adj[a2].push(a1); } // Function to convert the given tree // into a bipartite graph using BFS function toBipartite(N) { // Stores the current node during // the BFS traversal of the tree let q = []; // Initialize the set number of // 1st node and enqueue it q.push(0); setNum[0] = 0; // BFS traversal of the given tree while (q.length > 0) { // Current node let v = q[0]; q.shift(); // Traverse over all neighbors // of the current node for (let u of adj[v]) { // If the set is not assigned if (setNum[u] === -1) { // Assign set number to node u setNum[u] = setNum[v] ^ 1; q.push(u); } } } } // Function to find if the path length // between node A and B is even or odd function pathLengthQuery(A, B) { // If the set number of both nodes is // same, path length is odd else even if (setNum[A] === setNum[B]) { document.write("Odd"); } else { document.write("Even"); } } // Driver Code let N = 7; addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(3, 4); addEdge(3, 5); addEdge(2, 6); // Function to convert tree into // bipartite toBipartite(N); pathLengthQuery(4, 2); pathLengthQuery(0, 4); // This code is contributed by Potta Lokesh </script> |
Output:
Odd Even
Time Complexity: O(N + Q)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
