想了一想幾個(gè)月前打的用于解LCA的Tarjan貌似棄坑就沒(méi)再管它，然后虛擬機(jī)磁盤被我莫名其妙起爆了以后之前打的程序全都打了水漂就想起了被置之不理的Tarjan解LCA問(wèn)題的板子，索性就把坑填上唄，畢竟我不是挖坑不填的主 明明還有一堆亂七八糟的平衡樹(shù)沒(méi)填 LCA就是樹(shù)上兩點(diǎn)的最近公共祖先。說(shuō)這個(gè)之前，得先了解一下什么是樹(shù)上兩點(diǎn)的公共祖先。 就比如上圖中根節(jié)點(diǎn)為t[1]的樹(shù)，在其上的節(jié)點(diǎn)t[4]和t[5]有兩個(gè)公共祖先，一個(gè)是它們共有的父親t[3]，一個(gè)是它們共有的父親的父親t[1]。如果深度大一點(diǎn)，從它們最開(kāi)始共有的祖先，即最近公共祖先(LCA)及它們的LCA的所有祖先都是它們的公共祖先。自然，根節(jié)點(diǎn)是以它為根的樹(shù)上任意兩點(diǎn)的公共祖先。 然而求公共祖先并沒(méi)有什么用。我們所要的只是它們的LCA而已，也就是它們的公共祖先中深度最大的那個(gè)節(jié)點(diǎn)。在線算法有ST，不過(guò)在這里我求LCA用的算法是離線的Tarjan。 Tarjan算法是建立在一個(gè)深度優(yōu)先搜索(DFS)上的，它把每一個(gè)點(diǎn)對(duì)的問(wèn)題都統(tǒng)計(jì)完后通過(guò)對(duì)整棵樹(shù)一遍DFS解決所有問(wèn)題然后輸出結(jié)果。這也是它較暴力算法時(shí)間復(fù)雜度大幅降低的原因。 在通過(guò)鄰接表的方式(畢竟你也不知道它是幾叉樹(shù))把樹(shù)存儲(chǔ)完以后，我們把要求求LCA的所有點(diǎn)對(duì)連接起來(lái)(自然也是鄰接表存儲(chǔ)噠)做出另一個(gè)圖，就像紅色線所標(biāo)識(shí)的那樣: 這樣子我們就有了一個(gè)問(wèn)題集合的無(wú)向圖。然后我們就可以從根節(jié)點(diǎn)開(kāi)始遍歷整棵樹(shù)，圖上就是從t[1]開(kāi)始。途中用f[x]的方式記錄當(dāng)前情況下x所在集合的代表，這個(gè)可以用并查集解決。 在DFS到t[x]時(shí)我們先初始化f[x]=x，并令vis[x]=true。按照問(wèn)題的鄰接表查詢一下含有t[x]點(diǎn)的每個(gè)問(wèn)題，如果點(diǎn)對(duì)中另一個(gè)點(diǎn)t[y]已經(jīng)走過(guò)了(可以開(kāi)個(gè)bool類型的vis數(shù)組解決此問(wèn)題)，那就把相應(yīng)標(biāo)號(hào)的問(wèn)題寫(xiě)上解為find(y)（就是并查集find()操作啦），否則不予置理。之后我們遍歷一遍與t[x]相連的樹(shù)上的所有邊，只要與t[x]相連的點(diǎn)t[z]的vis[z]=false，t[z]就必定是t[x]的兒子之一，我們就可以遞歸再搜索一遍t[z]，搜索完后令f[z]=x，直到遍歷完整棵樹(shù)。 因?yàn)樵诎颜脴?shù)遍歷的過(guò)程中，我們手推一下就能知道以節(jié)點(diǎn)t[x]為根的樹(shù)中所有節(jié)點(diǎn)都遍歷過(guò)之前，f[x]一定是x，所以可以得出只要是已經(jīng)能解決的要求就必定是最近的公共祖先的結(jié)論。LCA問(wèn)題也就解決了。 最后例行上代碼：