Simple example of finding the lowest common ancestor. The range minimum query is done in O(n) time, but can be done in O(log(n)) time with a O(n*log(n)) precomputation, with a e.g. a segment tree.

gistfile1.cpp

#include <vector>
#include <climits>
using namespace std;

int iteration = 0;
vector<size_t> h, l, e;
vector<vector<size_t> > adj;

void lca_dfs(size_t v, size_t depth)
{
  if(h[v] == -1)
    h[v] = iteration;

  e[iteration] = v;
  l[iteration++] = depth;

  for(vector<size_t>::iterator u = adj[v].begin();
      u != adj[v].end(); u++)
  {
    // Just because our graph is bidirectional,
    // we check if we've visited it before, so we don't
    // go infinite.
    if(h[*u] == -1)
    {
      lca_dfs(*u, depth + 1);

      // Back at parent
      e[iteration] = v;
      l[iteration++] = depth;
    }
  }
}

size_t lca(size_t v, size_t w)
{
  int min_depth_iteration = -1;
  int min_depth = INT_MAX;

  // Naive RMQ, #yolo
  for(int i = h[v]; i <= h[w]; i++) {
    if(l[i] < min_depth) {
      min_depth = l[i];
      min_depth_iteration = i;
    }
  }

  // Now min_depth_iteration is the iteration
  // at which we have the minimum depth
  // return whatever node was present at that iteration
  return e[min_depth_iteration];
}

int main()
{
  return 0;
}

gistfile2.md

0 1 2 3 4 5 6  7   8 9  10 11 12 13 14
h: 0 0 1 9 2 4 10 12 
e: 1 2 4 2 5 8 5  2   1 3  6  3  7  3  1 
l: 0 1 2 1 2 3 2  1   0 1  2  1  2  1  0