最近公共祖先(LCA)

最近公共祖先LCA(Tarjan算法)的思考和算法实现 - JVxie - 博客园 (cnblogs.com)

概念

最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。

换句话说，就是两个点在这棵树上距离最近的公共祖先节点。

LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。

前置知识并查集

1
2
3
4
5
6
7
8
9
10
11
12
int fa[100000];
void reset(){
    for (int i=1;i<=100000;i++){
        fa[i]=i;
    }
}
int getfa(int x){
    return fa[x]==x?x:getfa(fa[x]);
}
void marge(int x,int y){
    fa[getfa(y)]=getfa(x);
}

向上标记法

姑且算个方法

向上标记法是求 LCA 最直接的方法，直接根据定义来求，单次查询的时间复杂度最坏为 O (n)

算法流程：

  1. 从 x 节点向上一直走到根节点，沿途标记经过的节点
  2. 从 y 节点向上一直走到根节点，当第一次遇到已标记的节点时，该节点就是 LCA(x,y）

算法一：

tarjan算法离线算法

离线算法，是指首先读入所有的询问（求一次LCA叫做一次询问），然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解决LCA问题的离线算法，它结合了深度优先遍历和并查集，整个算法为线性处理时间。

  1. 任选一个点为根节点，从根节点开始。
  2. 遍历该点u所有子节点v，并标记这些子节点v已被访问过。
  3. 若是v还有子节点，返回2，否则下一步。
  4. 合并v到u上。
  5. 寻找与当前点u有询问关系的点v。
  6. 若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

举例：

img

下面开始模拟过程：

取1为根节点，往下搜索发现有两个儿子2和3；

先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；

发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以不操作；

发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；

img

表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;

先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其有关系的点；

发现8和9有关系，但是vis[8]=0,即8没被搜到过，所以不操作；

发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；

表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找与其有关系的点；

发现5和7有关系，但是vis[5]=0，所以不操作；

发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；

img

表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；

发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为find(9)=5；

(find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;)

发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1；

表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；

img

发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5；

(find(7)的顺序为f[7]=5-->f[5]=5 return 5;)

又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全部搜完了；

返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；

发现2没有未被搜完的子节点，寻找与其有关系的点；

又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；

img

表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；

搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；

此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;

(find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;)

发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已经被搜完

img

更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；

发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为find(5)=1；

(find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;)

发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；

img

更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。

存起来输出的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef unsigned long long ll;
const int N = 5e+5+100;
typedef pair<int,int> PII;
int n,m,vis[N],fa[N],lca[N];
vector<int>g[N];
vector<PII>query[N];
int find(int x)  //并查集的find函数
{
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
void tarjan(int q)  //q表示当前遍历的节点
{
    vis[q]++;  //标记为1
    for(int t:g[q])  //枚举子节点
    {
        if(!vis[t])  //如果子节点还没有被访问
        {
            tarjan(t);     //遍历子节点
            fa[t] = q;    //合并子节点到当前节点
        }
    }
    for(auto t:query[q])//与q结点有关的询问t.second是问题编号，t.first是询问的另一个结点
    {
        int v = t.x, id = t.y;
        if(vis[v] == 2 && !lca[id])  //如果第id个问题还没有找到lca并且v节点已回溯
        {
            lca[id] = find(v);
        }

    }
    vis[q]++;  //标记为2 表示已回溯
}
int main()
{
    int s;
    cin >> n >> m >> s;
    for(int i = 1; i < n; i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) fa[i] = i;

    for(int i = 1; i <= m; i++)
    {
        int a,b;
        cin>>a>>b;
        if(a == b)
        {
            lca[i] = a;
            continue;
        }
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }
    tarjan(s);
    for(int i = 1; i <= m; i++)
    {
        cout<<lca[i]<<'\n';
    }

    return 0;
}

算法二：倍增LCA

何为倍增？

所谓倍增，就是按2的倍数来增大

如果大的跳不过去，再把它调小。这是因为从小开始跳，可能会出现“悔棋”的现象。

用树上倍增法求 LCA 的时间复杂度为 O ((n+m) logn)

树上倍增法用到了二进制拆分的思想。在求 LCA 时，用 f [i] [j] 存储 i 的第 2 的 j 次方辈祖先的节点编号，特别地，若该节点不存在，则将值定为 0。根据这个定义，可以推出以下的递推式：

1
f[i][j]=f[f[i][j-1]][j-1];

一个节点的 f 数组的值要通过它的祖先节点转移过来，因此我们在递推时要采用从根到叶子的遍历。普遍使用的方法有 dfs 和 bfs，在这里我们用 bfs 来实现。

步骤：

  1. 建立一个空队列，并将根节点入队，同时存储根节点的深度
  2. 取出队头，遍历其所有出边。由于存储的时候是按照无向图存储，因此要进行深度判定，对于连接到它父亲节点的边，直接 continue 即可。记当前路径的另一端节点为 y，处理出 y 的 d、f 两个数组的值，然后将 y 入队。
  3. 重复第 2 步，直到队列为空

以上部分是树上倍增法的预处理，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
const int N=6e5;
int n,m,s,t,tot=0,f[N][20],d[N],ver[2*N],Next[2*N],head[N];
queue<int> q;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void bfs()
{
    q.push(s);
    d[s]=1;//将根节点入队并标记
    while(q.size())
    {
        int x=q.front();q.pop();//取出队头
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            if(d[y])
                continue;
            d[y]=d[x]+1;
            f[y][0]=x;//初始化，因为y的父亲节点就是x
            for(int j=1;j<=t;j++)
                f[y][j]=f[f[y][j-1]][j-1];//递推f数组
            q.push(y);
        }
    }
}
int lca(int x,int y)
{
    if(d[x]>d[y])
        swap(x,y);
    //保证顺序
    for(int i=t;i>=0;i--)
        if(d[f[y][i]]>=d[x])
            y=f[y][i];//尝试上移y
    if(x==y)
        return x;//若相同说明找到了LCA
    for(int i=t;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i],y=f[y][i];
        }//尝试上移x、y并保持它们不相遇
    return f[x][0];//当前节点的父节点即为LCA
}
int main()
{
    cin>>n>>m>>s;
    t=log2(n)+1;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
        //添加边的过程
    }
    bfs();
    while(m--)
    {
        int a,b;
        cin>>a>>b;
 cout<<lca(a,b)<<'\n';
    }
    return 0;
}