Check if XOR of each connected component becomes equal after removing atmost P edges
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 tree vector< int > adj[N]; // array arr defined to store node values // array cal_XOR defined to store // xor values rooted at i'th level int nodes[N], cal_XOR[N]; // defined a visited array vector< bool > visited(N); // defined a counter to store // number of subtrees having value equal // to whole tree XOR int counter = 0; // first dfs function to find // xor of subtrees 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 ( 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 point 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 ( 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 edges void addEdge( int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // Function to take input // for (n-1) edges void 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 Code int 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 equal import 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 equal N = int ( 1e5 ) # adjacency list to form a tree adj = [[] for _ in range (N)] # array arr defined to store node values # array cal_XOR defined to store # xor values rooted at i'th level nodes, cal_XOR = [ 0 for _ in range (N)], [ 0 for _ in range (N)] # defined a visited array visited = [ 0 for _ in range (N)] # defined a counter to store # number of subtrees having value equal # to whole tree XOR counter = 0 # first dfs function to find # xor of subtrees def 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 point def 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 edges def 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) edges def 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 Code if __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> |
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