上面是個草圖，特別草

假設(shè)現(xiàn)在u = 13號結(jié)點，此時按照tarjan算法，2,5,11,12結(jié)點作為一類，但是此類的標(biāo)簽不一定是2，所以必須用單獨的ancestor指定此類的根結(jié)點是2；6號結(jié)點單獨作為一類，13,17,18作為一類，其他結(jié)點都是各自作為一類，如果要求13和11的最近公共結(jié)點，只要求11所在類的根結(jié)點，即2，以此根結(jié)點作為最近公共結(jié)點；同理，13與2,5,11,12的最近公共結(jié)點都是2(但是現(xiàn)在還不能求出13和2的公共節(jié)點，因為2的所有分支還沒有遍歷完)；但是現(xiàn)在還求不出來13和6的公共結(jié)點，因為這時vist[6] = 0,所以還不能求；當(dāng)算法繼續(xù)運行，回溯至6結(jié)點，此時6,13,17,18作為一類，這個類的根結(jié)點是6，所以此時就可以求6和13的最近公共結(jié)點，就是求出13的根結(jié)點（因為這時vist[13] = 1），也就是6;

tarjan算法可以看做后序遍歷，只有當(dāng)前節(jié)點u的所有分支都訪問完之后，才將vist[u] = 1,表示u已經(jīng)訪問過了。

依次訪問當(dāng)前節(jié)點u的所有孩子節(jié)點，訪問完一個就把這個分支的節(jié)點和節(jié)點u標(biāo)注為一類，并且注明這個類的代表就是u;這樣依次把u的孩子節(jié)點并入以u為代表的類中。

要注意，雖然把u和其孩子節(jié)點并入一類，但是在訪問完u的所有孩子之前，u還是沒有被訪問過的。

設(shè)當(dāng)前節(jié)點是13, 則13和6的lca不可求，這是因為6的孩子節(jié)點還沒有訪問完，6還是未訪問的。

下面是poj1330的代碼:

#include <vector> #include <stdio.h> #include <cstring> #include <iostream> using namespace std;const int MaxNode = 10001; vector<int> g[MaxNode]; vector<int> q[MaxNode];//用來記錄queryint f[MaxNode]; int r[MaxNode];//rank int indegree[MaxNode]; int ancestor[MaxNode]; bool vist[MaxNode];void Init(int n) {for (int i=1;i<=n;++i){f[i] = i;//各自為類r[i] = 1;g[i].clear();q[i].clear();} }void Merge(int a,int b) {int pa = f[a];int pb = f[b];if (pa!=pb){if (r[pa]>r[pb]){f[pb] = pa;}else//將pa的father變?yōu)閜b{f[pa] = pb;if (r[pa] == r[pb]){//pb的rank增大++r[pb];}}} }int Find(int a) {if(a!=f[a])f[a] = Find(f[a]);return f[a]; }void Tarjan(int u) {ancestor[u] = u;for (int i=0;i<g[u].size();++i){Tarjan(g[u][i]);Merge(u,g[u][i]);ancestor[Find(u)] = u;//merge之后，類別標(biāo)簽改變，但是必須保證這個類的根節(jié)點是u}vist[u] = true;//每當(dāng)一個節(jié)點的所有分支都遍歷結(jié)束時，就檢查與這個節(jié)點相連的查詢節(jié)點for (int i=0;i<q[u].size();++i){if(vist[q[u][i]]){cout<<ancestor[Find(q[u][i])]<<endl;return;}}}int main() {int Case;scanf("%d",&Case);int ind = 0;for (;ind<Case;++ind){int count;scanf("%d",&count);Init(count);memset(indegree,0,sizeof(indegree));memset(ancestor,0,sizeof(ancestor));memset(vist,0,sizeof(vist));int u,v;for (int i=0;i<count -1;++i){scanf("%d%d",&u,&v);g[u].push_back(v);++indegree[v];}scanf("%d%d",&u,&v);q[u].push_back(v);q[v].push_back(u);for (int i=1;i<=count;++i){if (indegree[i] ==0)//找到樹的根節(jié)點{Tarjan(i);}}}return 0; }
Tarjan算法雖然簡單，但是很少有資料說的清楚的，下面一段話摘自：http://dongxicheng.org/structure/lca-rmq/

Tarjan算法也要用到深度優(yōu)先搜索，算法大體流程如下：對于新搜索到的一個結(jié)點，首先創(chuàng)建由這個結(jié)點構(gòu)成的集合，再對當(dāng)前結(jié)點的每一個子樹進(jìn)行搜索，每搜索完一棵子樹，則可確定子樹內(nèi)的LCA詢問都已解決。其他的LCA詢問的結(jié)果必然在這個子樹之外，這時把子樹所形成的集合與當(dāng)前結(jié)點的集合合并，并將當(dāng)前結(jié)點設(shè)為這個集合的祖先。之后繼續(xù)搜索下一棵子樹，直到當(dāng)前結(jié)點的所有子樹搜索完。這時把當(dāng)前結(jié)點也設(shè)為已被檢查過的，同時可以處理有關(guān)當(dāng)前結(jié)點的LCA詢問，如果有一個從當(dāng)前結(jié)點到結(jié)點v的詢問，且v已被檢查過，則由于進(jìn)行的是深度優(yōu)先搜索，當(dāng)前結(jié)點與v的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包涵v的子樹一定已經(jīng)搜索過了，那么這個最近公共祖先一定是v所在集合的祖先。

總結(jié)

以上是生活随笔為你收集整理的lca---tarjan算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。