Given, a Tree with N nodes, and an integer P, the task is to remove at edges in range [1, P) and find the XOR of nodes for every connected component formed. If node’s values come out to be equal for all connected components formed, Print “YES” else “NO”.
Examples:
Input: N = 5, P = 5, Edges[][]={ { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 }}, nodes[] = {2, 2, 2, 2, 2}
Output: YES
Explanation: We can remove all edges, then there will be 5 connected components each having one node with value 2, thus XOR of each of them will be 2.
Input: N = 5, P = 2, Edges[][]={ { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 }}, nodes[] = {1, 6, 4, 1, 2}
Output: YES
Explanation: As, p = 2, atleast one edge need to be removed so, removing edge (4, 5), gives two connected components.
XOR of first component would be, arr1 XOR arr2 XOR arr3 XOR arr4= 1 XOR 6 XOR 4 XOR 1 => 2.
XOR of second component will be arr5 = 2. (Thus, both equal).
Approach: The approach to solve this problem is based on following observations:
The fact here, is that deletion of edges should be either once or twice, as:
- Removing one edge gives us 2 connected components, which should have same XOR and thus by properties of xor if XOR1 == XOR2, then XOR1 ^ XOR2 = 0, where ^ is the bitwise XOR.
- Similarly, if XOR of the whole tree is 0, removing any edge, will give 2 connected components where both components would have equal value, thus answer = “YES”.
- Now, if we delete 2 edges, deleting more than that would just merge the other components with each other. For ex: if there are 4 or more connected components, we can reduce and merge them, as for 4 it can be reduced to 2 components (which will fall in the case if we remove 1 edge).
- Now, deleting 2 edges gives us a minimum of 3 connected components, using properties of xor we know, that XOR1 ^ XOR2 ^ XOR3 = let’s say some value(y), which means we need to find such subtrees(or say search for 2 edges to remove) whose XOR is equal to some value(y), and if we find it then answer = “YES” else “NO”, such that p>2.
- For ex: say, if we have total XOR = some value(y), with N = 4, there can be 3 segments whose XOR would have been y, then the total elements could get XOR = y, such that p > 2.
So, overall it can be said that if we find two subtrees whose XOR = y, and if our total XOR was y, we can say that our left out component/segment XOR would also be y, thus answer = “YES”, such that p > 2, using above property XOR1 ^ XOR2 ^ XOR3 = some value(y),
Follow the steps below to apply the above approach:
To find such subtrees, with a minimum of 3 connected components, it can be done easily using DFS traversal and during backtracking, we will store each index XOR at each iteration.
Below is the implementation of the above approach:
C++
// C++ code for Check after removing// edges bitwise XOR of each connected// component formed is equal#include <bits/stdc++.h>using namespace std;const int N = 1e5;// adjacency list to form a treevector<int> adj[N];// array arr defined to store node values// array cal_XOR defined to store// xor values rooted at i'th levelint nodes[N], cal_XOR[N];// defined a visited arrayvector<bool> visited(N);// defined a counter to store// number of subtrees having value equal// to whole tree XORint counter = 0;// first dfs function to find// xor of subtreesint dfs_First(int x){ // initializing cal_XOR // array with tree node's value cal_XOR[x] = nodes[x]; // marking each visited node as true visited[x] = true; // iterating through current node children for (auto y : adj[x]) { // check if node->child is not visited if (!visited[y]) { // computing xor of subtree rooted at x cal_XOR[x] ^= dfs_First(y); } } // returning xor of subtree rooted at x return cal_XOR[x];}// second dfs function to count// subtrees having values equal// to entire XOR of tree nodes values// and returning subtree XOR till that pointint dfs_Second(int x){ // marking each visited node as true visited[x] = true; // storing value of nodes[x] // to another variable temp // for further calculation int temp = nodes[x]; // iterating through current node children for (auto y : adj[x]) { // check if node->child is not visited if (!visited[y]) { // storing xor of subtree temp ^= dfs_Second(y); } } // now, checking if xor of subtree // computed till now is equal to // entire XOR of tree (root) // i.e. value at cal_XOR[0] -> // which will give entire XOR of the tree if (temp == cal_XOR[0]) { // then, make that xor 0 temp = 0; // increase count by 1, which // means we found a subtree counter++; } // return xor of subtree // till that point return temp;}// Function to add edgesvoid addEdge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Function to take input// for (n-1) edgesvoid init(int edges[4][2], int numEdges){ for (int i = 0; i < numEdges; i++) { edges[i][0]--; edges[i][1]--; addEdge(edges[i][0], edges[i][1]); }}// Driver Codeint main(){ // taking input int n = 5, p = 2; nodes[0] = 1, nodes[1] = 6, nodes[2] = 4, nodes[3] = 1, nodes[4] = 2; // making our visited array false for (int i = 0; i < n; i++) { visited[i] = false; } // taking input for (n-1) edges int edges[4][2] = { { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } }; init(edges, 4); // First dfs Function call dfs_First(0); // again, marking visited array to false for (int i = 0; i < n; i++) { visited[i] = false; } // initializing answer variable bool answer = false; // if we found XOR of entire tree // equal to zero, answer = "YES", as // it means there are two connected // components equal to each other // thus, a single edge can be removed if (cal_XOR[0] == 0) { answer = true; } else { // second DFS function call dfs_Second(0); // if we found 2 subtree having // equal value with XOR of entire tree // answer is always "YES", such that // p > 2 if (counter >= 2 and p != 2) { answer = true; } } // printing the final answer if (answer == true) { cout << "YES" << "\n"; } else { cout << "NO" << "\n"; } // making counter = 0 for next iteration counter = 0; for (int i = 0; i < n; i++) { // similarly clearing adjacency list // and both arr and cal_XOR array adj[i].clear(); cal_XOR[i] = nodes[i] = 0; }} |
Java
// Java code for Check after removing// edges bitwise XOR of each connected// component formed is equalimport java.util.*;public class GFG { static int N = 100000; // adjacency list to form a tree static ArrayList<ArrayList<Integer> > adj = new ArrayList<>(); // array arr defined to store node values // array cal_XOR defined to store // xor values rooted at i'th level static int[] nodes = new int[N]; static int[] cal_XOR = new int[N]; // defined a visited array static boolean[] visited = new boolean[N]; // defined a counter to store // number of subtrees having value equal // to whole tree XOR static int counter = 0; // first dfs function to find // xor of subtrees static int dfs_First(int x) { // initializing cal_XOR // array with tree node's value cal_XOR[x] = nodes[x]; // marking each visited node as true visited[x] = true; // iterating through current node children for (Integer y : adj.get(x)) { // check if node->child is not visited if (!visited[y]) { // computing xor of subtree rooted at x cal_XOR[x] ^= dfs_First(y); } } // returning xor of subtree rooted at x return cal_XOR[x]; } // second dfs function to count // subtrees having values equal // to entire XOR of tree nodes values // and returning subtree XOR till that point static int dfs_Second(int x) { // marking each visited node as true visited[x] = true; // storing value of nodes[x] // to another variable temp // for further calculation int temp = nodes[x]; // iterating through current node children for (Integer y : adj.get(x)) { // check if node->child is not visited if (!visited[y]) { // storing xor of subtree temp ^= dfs_Second(y); } } // now, checking if xor of subtree // computed till now is equal to // entire XOR of tree (root) // i.e. value at cal_XOR[0] -> // which will give entire XOR of the tree if (temp == cal_XOR[0]) { // then, make that xor 0 temp = 0; // increase count by 1, which // means we found a subtree counter++; } // return xor of subtree // till that point return temp; } // Function to add edges static void addEdge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } // Function to take input // for (n-1) edges static void init(int[][] edges, int numEdges) { for (int i = 0; i < numEdges; i++) { edges[i][0]--; edges[i][1]--; addEdge(edges[i][0], edges[i][1]); } } // Driver Code public static void main(String[] args) { // taking input int n = 5, p = 2; nodes[0] = 1; nodes[1] = 6; nodes[2] = 4; nodes[3] = 1; nodes[4] = 2; for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } // taking input for (n-1) edges int[][] edges = { { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } }; init(edges, 4); // First dfs Function call dfs_First(0); // again, marking visited array to false for (int i = 0; i < n; i++) { visited[i] = false; } // initializing answer variable boolean answer = false; // if we found XOR of entire tree // equal to zero, answer = "YES", as // it means there are two connected // components equal to each other // thus, a single edge can be removed if (cal_XOR[0] == 0) { answer = true; } else { // second DFS function call dfs_Second(0); // if we found 2 subtree having // equal value with XOR of entire tree // answer is always "YES", such that // p > 2 if (counter >= 2 && p != 2) { answer = true; } } // printing the final answer if (answer == true) { System.out.println("YES"); } else { System.out.println("NO"); } // making counter = 0 for next iteration counter = 0; for (int i = 0; i < n; i++) { // similarly clearing adjacency list // and both arr and cal_XOR array adj.get(i).clear(); cal_XOR[i] = nodes[i] = 0; } }}// This code is contributed by karandeep1234. |
Python3
# python3 code for Check after removing# edges bitwise XOR of each connected# component formed is equalN = int(1e5)# adjacency list to form a treeadj = [[] for _ in range(N)]# array arr defined to store node values# array cal_XOR defined to store# xor values rooted at i'th levelnodes, cal_XOR = [0 for _ in range(N)], [0 for _ in range(N)]# defined a visited arrayvisited = [0 for _ in range(N)]# defined a counter to store# number of subtrees having value equal# to whole tree XORcounter = 0# first dfs function to find# xor of subtreesdef dfs_First(x): global N, adj, nodes, cal_XOR, visited, counter # initializing cal_XOR # array with tree node's value cal_XOR[x] = nodes[x] # marking each visited node as true visited[x] = True # iterating through current node children for y in adj[x]: # check if node->child is not visited if (not visited[y]): # computing xor of subtree rooted at x cal_XOR[x] ^= dfs_First(y) # returning xor of subtree rooted at x return cal_XOR[x]# second dfs function to count# subtrees having values equal# to entire XOR of tree nodes values# and returning subtree XOR till that pointdef dfs_Second(x): global N, adj, nodes, cal_XOR, visited, counter # marking each visited node as true visited[x] = True # storing value of nodes[x] # to another variable temp # for further calculation temp = nodes[x] # iterating through current node children for y in adj[x]: # check if node->child is not visited if (not visited[y]): # storing xor of subtree temp ^= dfs_Second(y) # now, checking if xor of subtree # computed till now is equal to # entire XOR of tree (root) # i.e. value at cal_XOR[0] -> # which will give entire XOR of the tree if (temp == cal_XOR[0]): # then, make that xor 0 temp = 0 # increase count by 1, which # means we found a subtree counter += 1 # return xor of subtree # till that point return temp# Function to add edgesdef addEdge(u, v): global N, adj, nodes, cal_XOR, visited, counter adj[u].append(v) adj[v].append(u)# Function to take input# for (n-1) edgesdef init(edges, numEdges): global N, adj, nodes, cal_XOR, visited, counter for i in range(0, numEdges): edges[i][0] -= 1 edges[i][1] -= 1 addEdge(edges[i][0], edges[i][1])# Driver Codeif __name__ == "__main__": # taking input n, p = 5, 2 nodes[0], nodes[1], nodes[2] = 1, 6, 4 nodes[3], nodes[4] = 1, 2 # making our visited array false for i in range(0, n): visited[i] = False # taking input for (n-1) edges edges = [[1, 2], [2, 3], [1, 4], [4, 5]] init(edges, 4) # First dfs Function call dfs_First(0) # again, marking visited array to false for i in range(0, n): visited[i] = False # initializing answer variable answer = False # if we found XOR of entire tree # equal to zero, answer = "YES", as # it means there are two connected # components equal to each other # thus, a single edge can be removed if (cal_XOR[0] == 0): answer = True else: # second DFS function call dfs_Second(0) # if we found 2 subtree having # equal value with XOR of entire tree # answer is always "YES", such that # p > 2 if (counter >= 2 and p != 2): answer = True # printing the final answer if (answer == True): print("YES") else: print("NO") # making counter = 0 for next iteration counter = 0 for i in range(0, n): # similarly clearing adjacency list # and both arr and cal_XOR array adj[i] = [] cal_XOR[i] = nodes[i] = 0 # This code is contributed by rakeshsahni |
C#
// C# code for Check after removing // edges bitwise XOR of each connected // component formed is equal using System; using System.Collections; using System.Collections.Generic; public class GFG { // adjacency list to form a tree static List<int>[] adj = new List<int>[10000]; // array arr defined to store node values // array cal_XOR defined to store // xor values rooted at i'th level static int[] nodes = new int[10000]; static int[] cal_XOR = new int[10000]; // defined a visited array static bool[] visited = new bool[10000]; // defined a counter to store // number of subtrees having value equal // to whole tree XOR static int counter = 0; // first dfs function to find // xor of subtrees static int dfs_First(int x) { // initializing cal_XOR // array with tree node's value cal_XOR[x] = nodes[x]; // marking each visited node as true visited[x] = true; // iterating through current node children for (int i = 0; i < adj[x].Count; i++) { // check if node->child is not visited if (!visited[adj[x][i]]) { // computing xor of subtree rooted at x cal_XOR[x] ^= dfs_First(adj[x][i]); } } // returning xor of subtree rooted at x return cal_XOR[x]; } // second dfs function to count // subtrees having values equal // to entire XOR of tree nodes values // and returning subtree XOR till that point static int dfs_Second(int x) { // marking each visited node as true visited[x] = true; // storing value of nodes[x] // to another variable temp // for further calculation int temp = nodes[x]; // iterating through current node children for (int i = 0; i < adj[x].Count; i++) { // check if node->child is not visited if (!visited[adj[x][i]]) { // storing xor of subtree temp ^= dfs_Second(adj[x][i]); } } // now, checking if xor of subtree // computed till now is equal to // entire XOR of tree (root) // i.e. value at cal_XOR[0] -> // which will give entire XOR of the tree if (temp == cal_XOR[0]) { // then, make that xor 0 temp = 0; // increase count by 1, which // means we found a subtree counter++; } // return xor of subtree // till that point return temp; } // Function to add edges static void addEdge(int u, int v) { adj[u].Add(v); adj[v].Add(u); } // Function to take input // for (n-1) edges static void init(int[,] edges, int numEdges) { for (int i = 0; i < numEdges; i++) { edges[i,0]--; edges[i,1]--; addEdge(edges[i,0], edges[i,1]); } } // Driver Code public static void Main() { // taking input int n = 5, p = 2; nodes[0] = 1; nodes[1] = 6; nodes[2] = 4; nodes[3] = 1; nodes[4] = 2; // making our visited array false for (int i = 0; i < n; i++) { visited[i] = false; adj[i] = new List<int>(); } // taking input for (n-1) edges int[,] edges = new int[4,2] { { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } }; init(edges, 4); // First dfs Function call dfs_First(0); // again, marking visited array to false for (int i = 0; i < n; i++) { visited[i] = false; } // initializing answer variable bool answer = false; // if we found XOR of entire tree // equal to zero, answer = "YES", as // it means there are two connected // components equal to each other // thus, a single edge can be removed if (cal_XOR[0] == 0) { answer = true; } else { // second DFS function call dfs_Second(0); // if we found 2 subtree having // equal value with XOR of entire tree // answer is always "YES", such that // p > 2 if (counter >= 2 && p != 2) { answer = true; } } // printing the final answer if (answer == true) Console.Write("YES\n"); else Console.Write("NO\n"); // making counter = 0 for next iteration counter = 0; for (int i = 0; i < n; i++) { // similarly clearing adjacency list // and both arr and cal_XOR array adj[i].Clear(); cal_XOR[i] = nodes[i] = 0; } } // This code is contributed by Kanishka Gupta} |
Javascript
<script> // JavaScript code for the above approach let N = 1e5; // adjacency list to form a tree let adj = new Array(N); for (let i = 0; i < N; i++) { adj[i] = []; } // array arr defined to store node values // array cal_XOR defined to store // xor values rooted at i'th level let nodes = new Array(N), cal_XOR = new Array(N); // defined a visited array let visited = new Array(N).fill(false); // defined a counter to store // number of subtrees having value equal // to whole tree XOR let counter = 0; // first dfs function to find // xor of subtrees function dfs_First(x) { // initializing cal_XOR // array with tree node's value cal_XOR[x] = nodes[x]; // marking each visited node as true visited[x] = true; // iterating through current node children for (let y of adj[x]) { // check if node->child is not visited if (!visited[y]) { // computing xor of subtree rooted at x cal_XOR[x] ^= dfs_First(y); } } // returning xor of subtree rooted at x return cal_XOR[x]; } // second dfs function to count // subtrees having values equal // to entire XOR of tree nodes values // and returning subtree XOR till that point function dfs_Second(x) { // marking each visited node as true visited[x] = true; // storing value of nodes[x] // to another variable temp // for further calculation let temp = nodes[x]; // iterating through current node children for (let y of adj[x]) { // check if node->child is not visited if (!visited[y]) { // storing xor of subtree temp ^= dfs_Second(y); } } // now, checking if xor of subtree // computed till now is equal to // entire XOR of tree (root) // i.e. value at cal_XOR[0] -> // which will give entire XOR of the tree if (temp == cal_XOR[0]) { // then, make that xor 0 temp = 0; // increase count by 1, which // means we found a subtree counter++; } // return xor of subtree // till that point return temp; } // Function to add edges function addEdge(u, v) { adj[u].push(v); adj[v].push(u); } // Function to take input // for (n-1) edges function init(edges, numEdges) { for (let i = 0; i < numEdges; i++) { edges[i][0]--; edges[i][1]--; addEdge(edges[i][0], edges[i][1]); } } // Driver Code // taking input let n = 5, p = 2; nodes[0] = 1, nodes[1] = 6, nodes[2] = 4, nodes[3] = 1, nodes[4] = 2; // making our visited array false for (let i = 0; i < n; i++) { visited[i] = false; } // taking input for (n-1) edges let edges = [[1, 2], [2, 3], [1, 4], [4, 5]]; init(edges, 4); // First dfs Function call dfs_First(0); // again, marking visited array to false for (let i = 0; i < n; i++) { visited[i] = false; } // initializing answer variable let answer = false; // if we found XOR of entire tree // equal to zero, answer = "YES", as // it means there are two connected // components equal to each other // thus, a single edge can be removed if (cal_XOR[0] == 0) { answer = true; } else { // second DFS function call dfs_Second(0); // if we found 2 subtree having // equal value with XOR of entire tree // answer is always "YES", such that // p > 2 if (counter >= 2 && p != 2) { answer = true; } } // printing the final answer if (answer == true) { document.write("YES" + '<br>') } else { document.write("NO" + '<br>') } // making counter = 0 for next iteration counter = 0; for (let i = 0; i < n; i++) { // similarly clearing adjacency list // and both arr and cal_XOR array adj[i] = []; cal_XOR[i] = nodes[i] = 0; } // This code is contributed by Potta Lokesh </script> |
Output
YES
Time Complexity: O(N+E), where N= number of nodes, and E = number of edges
Auxiliary Space: O(N+E), where N= number of nodes, and E = number of edges
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!