efficiently calculate nearest common ancestor in a family tree (each person has two parents)
Just do breadth-first search up the graph, colouring each person you meet as being an ancestor of one person or the other, and stop when you reach a person who's an ancestor of both. You should do the searches in parallel (one generation back on one person, then one generation back on the other, and so on) because any common ancestor will be approximately the same number of generations back on each side.

Indeed, this is exactly what you should do on a tree: going all the way back to the root and then discarding all common ancestors after the first takes more time.