Function test

code/graph/tarjan_olca.test.cpp:132–168

};

void test() {
  int tests = 100;

  for (int t = 0; t < tests; t++) {
    int n = rng() % 10000 + 1;
    int q = rng() % 10000 + 1;

    pair<vi*, int> xadj = random_tree(n);
    vi *adj = xadj.first;
    int root = xadj.second;

    int *ps = pars(n, adj);

    lca_tree tr(n, root, adj);
    tarjan_olca lca(n, adj);

    vii qs;
    for (int i = 0; i < q; i++) {
      int a = rng() % n,
        b = rng() % n;

      qs.push_back(ii(a, b));
      lca.query(a, b);
    }

    lca.process(root);

    for (int i = 0; i < q; i++) {
      int correct = lca_slow(n, ps, qs[i].first, qs[i].second);
      int maybe = lca.answers[i];
      int maybe2 = tr.lca(qs[i].first, qs[i].second);
      assert_equal(correct, maybe);
      assert_equal(correct, maybe2);
    }
  }

}
// vim: cc=60 ts=2 sts=2 sw=2: