×

NPLFSGL-Editorial

Author: Vinod Tester: Vinod Editorialist: Manjunath

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.
for(int i=m;i>=1;i--){
//u-v is being unblocked
if(set(u)==set(v)){
ans[i-1]=ans[i];
}
else{
ans[i-1]=ans[i]-value(set(u))-value((set(v));
union(u,v);
value(set(u))=value(set(u))^value((set(v));
ans[i-1]+=value(set(u));
}
}


AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here. Tester's solution can be found here.

1287
accept rate: 8%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×66
×8

question asked: 12 Nov '17, 12:29

question was seen: 184 times

last updated: 12 Nov '17, 12:29