LCA 算法學習 （最近公共祖先）poj 1330

LCA 算法學習 （最近公共祖先）poj 1330

poj1330

在求解最近公共祖先為問題上，用到的是Tarjan的思想，從根結點開始形成一棵深搜樹，處理技巧就是在回溯到結點u的時候，u的子樹已經遍歷，這時候才把u結點放入合並集合中，這樣u結點和所有u的子樹中的結點的最近公共祖先就是u了，u和還未遍歷的所有u的兄弟結點及子樹中的最近公共祖先就是u的父親結點。這樣我們在對樹深度遍歷的時候就很自然的將樹中的結點分成若干的集合，兩個集合中的所屬不同集合的任意一對頂點的公共祖先都是相同的，也就是說這兩個集合的最近公共祖先只有一個。時間復雜度為O（n+q），n為節點，q為詢問節點對數。

#include"stdio.h"
#include"string.h"
#include"vector"
using namespace std;
#define N 11000
const int inf=1<<20;
vectorg[N];
int s,t,n;
int f[N],pre[N],ans[N];
bool vis[N];
int findset(int x)
{
    if(x!=f[x])
        f[x]=findset(f[x]);
    return f[x];
}
int unionset(int a,int b)
{
    int x=findset(a);
    int y=findset(b);
    if(x==y)
        return x;
    f[y]=x;
    return x;
}
void lca(int u)
{
    int i,v;
    ans[u]=u;
    for(i=0;i