最近在刷面试算法题是看到了这样一题:最近公共祖先祖先

也就是大家喜闻乐见的LCA问题,这个问题有许多种处理方法,比如Tarjan离线算法,倍增 ,线段树处理什么的…

由于这题数据比较水,对于每一棵树只有一组测试点,所以我就简单的遍历处理了,最终也是过了。

But,我回想起了LCA问题的另一种解法:Tarjan离线处理。

说到这个算法我就不由想到了高二那个炎热的暑假,当班里的同学都满头大汗的教室里面补课时,我却跑到了宿城二中的空调房里面划水摸鱼蹭算法课。

大多数人的第一个图论算法都是最短路径问题,而我不是,在宿城二中的小姐姐旁边(啊她还夸过我长得帅QwQ),我学会了我的一个图论算法:LCA问题的Tarjan离线解法。

在应聘时的算法题中,绝对不会变态到考查这种方法,但是可以拿来在面试官面前装b,毕竟时间复杂度和能解决的范围又更深了一步。

下面就来介绍一下这个算法: