本文讲解用于求解最近公共祖先（Least Common Ancestor, LCA）的tarjan算法。
首先看最近公共祖先问题。对一棵给定的有根树，为了得知两点之间最短的路径，显然应当先从一点运动到它们的最近公共祖先，再直接运动到另一点。如果每条边只能经过一次，那么这就是唯一的路径。这时就需要确定这两点的最近公共祖先。对小规模的数据可以使用暴力算法，比如对一个点的所有祖先进行dfs，找到最近的、能到达另一点的那个祖先。但是这个算法本身效率就很低下，更不用提大规模数据的情形。
解决这一类问题有多种算法，可分为在线算法和离线算法两种。“在线”和“离线”是针对大规模数据的说法，在线算法是指对每个询问（即节点对）即时处理的算法，离线算法是指将所有询问存储起来以后统一处理的算法。在线和离线会造成复杂度的很大差异，通常来讲离线算法应当更快一些，因为离线情形掌握了更多的信息。这里要讲的tarjan算法是一种离线算法，复杂度为$O(n+p)$，其中$n$为树的节点数，$p$为询问数。
考虑优化上述的dfs。上述的dfs显然有许多浪费，因为上述过程中的所有节点只需要一次dfs就可以遍历完，而上述过程中dfs的次数却与深度成正比，这显然是没有很好地利用dfs的信息。仔细考虑dfs的过程，发现遍历在最近祖先处是一棵一棵子树进行的，也就是先遍历了含有节点1的子树，再遍历含有节点2的子树（假设1比2先遍历到），我们需要找到这两棵子树“分叉”的地方，而不考虑分叉处上面的情形。那么可以考虑这样做：针对当前的状态v，为遍历过的每个节点u打上一个标记，记录u和v从哪里开始“分叉”。如果这一操作可以在遍历到u时就做到，那么问题就解决了。显然初始值（刚遍历到u时的标记）是这个节点直接的父亲。当遍历完他父亲的所有子树后仍没有找到节点2时，应当返回它父亲的父亲继续搜索，那么该节点的标记也都应当变成他的父亲的父亲。这看起来需要再进行一次dfs从而效率和刚才一样低，但是可以用并查集解决这一问题。现在的过程变成，遍历到某一结点时，将他和他父亲合并（在并查集中成为父亲的子树）；当他父亲遍历完所有子树之后，将他父亲和他父亲的父亲合并…为了知道某个节点的标记（分叉处），只需要查找该节点在并查集中的根节点。