LCAのtarjanアルゴリズム--まとめ

LCA問題、すなわち最近の共通祖先問題には、STテーブルへのオンライン変換アルゴリズム、ツリー上倍増アルゴリズム、オフラインtarjanアルゴリズムなど、多くの解法があります.オンラインのアルゴリズムはすべて簡単で、ここではオフラインのtarjanアルゴリズムについて話します.
思想
tarjanアルゴリズムも実は理解しにくくなくて、その主な思想はDFSの深さの優先する順序を利用して、アルゴリズムの主な枠組みは1つのDFS遍歴で、同時にそして調査集の急速な合併を利用しました.理解する時DFSの過程を分割することができて、1つのノードにアクセスする過程をそれに分割してアクセスを終了して、アクセスを終了して遡及して、DFSの順序はすべての経路が最後まで歩いて、それから1歩後退して、更に上の階の他の息子にアクセスして、更に後退して、更に上の階の上の階の他の息子にアクセスします......、セットのfa配列が記録されているのは、各ノードが現在どの点に遡っているかを調べます.各ノードについて、質問に関連する各質問にアクセスし、質問の別のノードがすでにアクセスしている場合、この質問の答えは別のノードのfa(現在遡及されているノード)です.ノードを検索するたびに、そのfaを親ノードとマージします(マージの順序に注意).
コード#コード#
poj 1330のコードは、以下に示す.

#include
#include
#include
#define maxn 10006
using namespace std;
int tet,n,tot,ans,Root,X,Y,fa[maxn],lnk[maxn],son[maxn],nxt[maxn];
bool vis[maxn],isR[maxn];
inline char nc(){
    static char buf[100000],*i=buf,*j=buf;
    return i==j&&(j=(i=buf)+fread(buf,1,100000,stdin),i==j)?EOF:*i++;
}
inline int _read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
void add(int x,int y){
    nxt[++tot]=lnk[x];son[tot]=y;lnk[x]=tot;
}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
void merge(int x,int y){
    x=get(x);y=get(y);
    if(x!=y)fa[x]=y;
}
void tarjan(int x){
    vis[x]=0;
    for(int j=lnk[x];j;j=nxt[j]) if(vis[son[j]]) tarjan(son[j]),merge(son[j],x);
    if(x==X&&!vis[Y])ans=get(Y);
    if(x==Y&&!vis[X])ans=get(X);
}
int main(){
    freopen("lca.in","r",stdin);
    freopen("lca.out","w",stdout);
    tet=_read();
    while(tet--){
        tot=0;memset(lnk,0,sizeof(lnk));memset(vis,1,sizeof(vis));memset(isR,1,sizeof(isR));
        n=_read();
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=1,x,y;i0;
        X=_read();Y=_read();
        for(int i=1;i<=n;i++) if(isR[i])Root=i;
        tarjan(Root);
        printf("%d
",ans);
    }
    return 0;
}