图论-最近公共祖先-Tarjan算法

Posted by

定义

最近公共祖先(LCA,Lowest Common Ancestors):对于有根树$latex T$的两个结点$latex u,v$,最近公共祖先表示$latex u$和$latex v$的深度最大的共同祖先。
Tarjan算法是求LCA的离线算法。

求解算法

思路

从根结点开始DFS,对遍历到的结点$latex u$标记已访问,创建新集合,元素为$latex u$,再遍历$latex u$的每一个子结点,回溯时将每个儿子的集合并到$latex u$的集合上,用并查集记录集合中的每个元素的$latex fa$为$latex u$,接着处理询问,对于关于$latex u$的每一个询问,若另一个结点$latex v$已访问,则可断定$latex LCA(u,v)$为$latex fa[v]$,记录结果,最后按顺序输出即可。
$latex dis[i]$存储该结点到根结点的距离,用于计算两点之间的路径长度。

样例推导

求$latex 8,6,9,7$的LCA;

从根结点$latex 1$进入,标记访问,创建集合;

访问$latex 2,4$,回溯到$latex 2$,新集合包含两个结点;

访问$latex 5,8$,处理$latex 8$的询问,但$latex 6$未访问,跳过;
访问$latex 9$,处理询问,$latex 7$未访问,跳过,$latex 5,8,9$并入$latex 2$的集合($latex fa[5]=fa[8]=fa[9]=2$);

访问$latex 6$,处理询问,$latex LCA(8,6)$为$latex fa[8]$,即$latex 2$;
访问$latex 10$,回溯,并入$latex 6$的集合;

回溯,并入$latex 2$的集合;
并入$latex 1$的集合;

访问$latex 3,7$,处理询问,$latex LCA(7,9)$为$latex fa[9]$,即$latex 1$;

回溯,并入$latex 3$的集合;
并入$latex 1$的集合。

实现

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注