PROBLEM LINK:Author: Vinod Tester: Vinod Editorialist: Manjunath DIFFICULTY:MEDIUM PREREQUISITES:graph,xor propery,union disjoint PROBLEM:batch power of graph is defined as sum of xor of all connected vertices.Each day one edge is being blocked (consider as removed).We have to find batch power on each day after removal. QUICK EXPLANATION:Instead of blocking, consider each day we are unblocking the edges. Then it is easy to solve this problem.so suppose previously 2 connected components x,y were there which were just connected by unblocking current edges.Then answer changes as ans=prev_ans(xor(x)+xor(y))+xor(x,y),where (x,y) denoted connected graph of x,y vertices.We can convert the actual problem to this variation by considering unblocking of edges from last day to the first day. EXPLANATION:Instead of blocking, consider each day we are unblocking the edges. Then it is easy to solve this problem.so suppose previously 2 connected components x,y were there which were just connected by unblocking current edges.Then answer changes as ans=prev_ans(xor(x)+xor(y))+xor(x,y),where (x,y) denoted connected graph of x,y vertices.We can convert the actual problem to this variation by considering unblocking of edges from last day to the first day. make each vertex as a disjoint set. value of disjoint set is xor of all vertices in that set. answer[m]=sum for(int i=m;i>=1;i){ //uv is being unblocked if(set(u)==set(v)){ ans[i1]=ans[i]; } else{ ans[i1]=ans[i]value(set(u))value((set(v)); union(u,v); value(set(u))=value(set(u))^value((set(v)); ans[i1]+=value(set(u)); } } AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. asked 12 Nov '17, 12:29
