Tarjan离线算法求最近公共祖先

Wong, LimstashOI

Tarjan 离线算法求最近公共祖先是通过并查集和dfs搜索实现的

算法思路[引]
[cc lang=”C++”]
Tarjan(u)//marge和find为并查集合并函数和查找函数
{
for each(u,v) //访问所有u子节点v
{
Tarjan(v); //继续往下遍历
marge(u,v); //合并v到u上
标记v被访问过;
}
for each(u,e) //访问所有和u有询问关系的e
{
如果e被访问过;
u,e的最近公共祖先为find(e);
}
}
[/cc]

 

用到了下面这些变量
[cc lang=”C++”]
int pre[MAXN]; //并查集
bool vis[MAXN]; //标记

int n,m;

vector <int> tree[MAXN]; //储存树
vector <int> query[MAXN]; //储存请求

[/cc]

 

Tarjan离线算法
[cc lang=”C++”]
void tarjan(int index,int fa){
for(int i=0;i<tree[index].size();i++){
int v = tree[index][i];

        if(v != fa){
            tarjan(v,index);
            merge(v,index);
            vis[v] = true;
        }
    }

    for(int i=0;i<query[index].size();i++){
        int v = query[index][i];

        if(vis[v]){
            printf("%d -- %d : %d\n",index,v,find(v));
        }
    }
}

[/cc]

 

并查集部分
[cc lang=”C++”]
int find(int root){
int x = root;

    while(root!=pre[root])
        root = pre[root];

    while(x!=root){
        int tmp = pre[x];
        pre[x] = root;
        x = tmp;
    }

    return x;
}

void merge(int x,int y){
    int father_x = find(x);
    int father_y = find(y);

    pre[father_x] = father_y;
}

[/cc]

 

初始化
[cc lang=”C++”]
void init(){
scanf(“%d%d”,&n,&m);

    for(int i=1;i<=n;i++)
        pre[i] = i;

    for(int i=0;i<n-1;i++){
        int u,v;

        scanf("%d%d",&u,&v);

        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    for(int i=0;i<m;i++){
        int u,v;

        scanf("%d%d",&u,&v);

        query[u].push_back(v);
        query[v].push_back(u);
    }
}

[/cc]