spaghetti-source / algorithm

C++ Implementation of Algorithms (aka. Spaghetti Source)

C++ implementations of algorithms

These are my C++ implementations of algorithms, which are written for studying/understanding algorithms.

These codes are published in public domain. You can use the codes for any purpose without any warranty.

author: Takanori MAEHARA (web: http://www.prefield.com, e-mail: [email protected], twitter: @tmaehara)

Recruiting

I am a researcher at RIKEN Center for Advanced Intelligence Project, which is a Japanese governmental academic research institute. I am working on discrete algorithms (including topics in this github repository). We are hiring strong programmers who has some achievements in some competitions. If you are interested in, please feel free to contact me.

algorithm's Issues

Bug of Euler Tour Tree

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.