-
Notifications
You must be signed in to change notification settings - Fork 159
Bug of Euler Tour Tree #18
Open
Description
Challenge case
int main() { euler_tour_tree ETT; auto a = ETT.make_node(1 << 0); auto b = ETT.make_node(1 << 1); auto c = ETT.make_node(1 << 2); auto ba = ETT.link(b, a); auto ca = ETT.link(c, a); ETT.cut(ba); // Now components are {a, c} and {b}. // Since b is a singleton component, there should be no child. cout << b->ch[0] << " " << b->ch[1] << endl; // expects 0 0 // Something undefined happens... auto ab = ETT.link(a, b); cout << ETT.sum_in_component(a) << endl; // expects 0b111 return 0; }
Cause
Here's the current implementation of cut operation.
algorithm/graph/euler_tour_tree.cc
Lines 99 to 103 in 4fdac82
void cut(node *uv) {
splay(uv); disconnect(uv,1); splay(uv->r);
join(disconnect(uv,0), disconnect(uv->r,1));
delete uv, uv->r;
}
This implementation assumes that uv->r is in the right subtree of uv after splay(uv). This assumption is true right after link(u, v), but not maintained in the following operations.
Metadata
Metadata
Assignees
Labels
No labels