Following the implementation of the disjointset, another fun algorithm to implement was the offline least common ancestor problem. Tarjan proposed a algorithm based on the disjoint-set and a DFS traversal. Given that I now have all those ingredients in QuickGraph, it was just a matter of hooking together the implementation with the right events. The beef of the implementation looks as follows (and looks quite elegant to me):

var gpair = GraphExtensions.ToAdjacencyGraph(this.pairs); // for fast lookup
var disjointSet = new ForestDisjointSet();
var vancestors = new Dictionary();
var dfs = new DepthFirstSearchAlgorithm(this, this.VisitedGraph, 
new DictionaryGraphColor>(this.VisitedGraph.VertexCount));

dfs.InitializeVertex += (sender, args) => disjointSet.MakeSet(args.Vertex);
dfs.DiscoverVertex += (sender, args) => vancestors[args.Vertex] = args.Vertex;
dfs.TreeEdge += (sender, args) =>
    {
        var edge = args.Edge;
        disjointSet.Union(edge.Source, edge.Target);
        vancestors[disjointSet.FindSet(edge.Source)] = edge.Source;
    };
dfs.FinishVertex += (sender, args) =>
    {
        foreach (var e in gpair.OutEdges(args.Vertex))
            if (dfs.VertexColors[e.Target] == GraphColor.Black)
                this.ancestors[EdgeExtensions.ToVertexPair(e)] = vancestors[disjointSet.FindSet(e.Target)];
    };

// go!
dfs.Compute(root);

Enjoy!