最近公共祖先（LCA）问题代码题解

一、题目背景

本题通过构建一个无向图（实际在后续处理中当作树结构来处理，因为需要确定根节点并基于树的深度和祖先关系来求解），实现求解图中任意两个节点的最近公共祖先（LCA），并根据最近公共祖先与这两个节点的关系进行相应输出。

二、代码整体架构

代码主要由以下几个部分组成：
1. 头文件和全局变量的定义，用于存储图的结构信息、节点深度、祖先关系等。
2. add 函数，用于向图中添加边。
3. bfs 函数，通过广度优先搜索来计算每个节点的深度以及各级祖先。
4. lca 函数，用于求解两个节点的最近公共祖先。
5. main 函数，负责读取输入数据，调用上述函数进行处理，并输出结果。

三、代码逐段分析

（一）头文件和全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];

1. 头文件：
   • #include <cstdio>：提供标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作，如 memset 函数。
   • #include <iostream>：提供 C++ 风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数，如 swap 和 max 等。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 40010：定义节点的最大数量。
   • const int M = N * 2：由于是无向图，边的最大数量是节点数量的两倍。
3. 变量定义：
   • int n, m;：n 表示输入的边的数量（在实际处理中可用于构建图），m 表示查询的次数。
   • int h[N], e[M], ne[M], idx;：用于构建邻接表存储图的结构。h[i] 表示节点 i 的第一条边在 e 和 ne 数组中的下标；e[j] 表示第 j 条边的另一端点；ne[j] 表示与第 j 条边同起点的下一条边的下标；idx 是边的计数器，用于记录当前已添加边的数量。
   • int depth[N], fa[N][16];：depth[i] 记录节点 i 在树中的深度；fa[i][k] 表示节点 i 的 2^k 级祖先（k 从 0 到 15），通过这种方式可以快速向上跳跃祖先节点。
   • int q[N];：作为队列，用于广度优先搜索（BFS）过程中存储待处理的节点。

（二）add 函数

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

该函数用于向邻接表中添加一条从节点 a 到节点 b 的边。具体操作是将节点 b 存储到 e[idx]，将原来节点 a 的第一条边的下标存储到 ne[idx]，然后更新 h[a] 为当前边的下标 idx，最后 idx 自增 1，以便添加下一条边。

（三）bfs 函数

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

1. 初始化：
   • memset(depth, 0x3f, sizeof depth);：将所有节点的深度初始化为一个较大的值（0x3f 表示十六进制的较大数，这里用于表示未访问过的节点深度）。
   • depth[0] = 0, depth[root] = 1;：将虚拟节点 0 的深度设为 0（这里的 0 节点是为了方便处理，实际无意义），根节点 root 的深度设为 1。
   • int hh = 0, tt = 0;：初始化队列的头指针 hh 和尾指针 tt 为 0。
   • q[0] = root;：将根节点 root 放入队列中。
2. BFS 过程：
   • while (hh <= tt)：当队列不为空时，进行循环。
   • int t = q[hh ++ ];：取出队头节点 t，并将头指针 hh 后移一位。
   • 对于节点 t 的每一条邻接边（通过 for (int i = h[t]; ~i; i = ne[i]) 遍历）：
     • 若邻接节点 j（j = e[i]）的深度大于节点 t 的深度加 1，说明找到了一条更短的路径到达节点 j。
     • 更新节点 j 的深度为 depth[t] + 1，将节点 j 加入队列（q[ ++ tt] = j;），并设置节点 j 的 0 级祖先为节点 t（fa[j][0] = t;）。
     • 通过内层循环 for (int k = 1; k <= 15; k ++ ) 计算节点 j 的 2^k 级祖先，利用递推关系 fa[j][k] = fa[fa[j][k - 1]][k - 1];，即节点 j 的 2^k 级祖先是节点 j 的 2^(k - 1) 级祖先的 2^(k - 1) 级祖先。

（四）lca 函数

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

1. 深度对齐：
   • if (depth[a] < depth[b]) swap(a, b);：确保节点 a 的深度大于等于节点 b 的深度，如果不是则交换 a 和 b。
   • 通过循环 for (int k = 15; k >= 0; k -- )，从 2^15 级祖先开始，若节点 a 的 2^k 级祖先的深度大于等于节点 b 的深度，则将节点 a 向上提升到其 2^k 级祖先（a = fa[a][k];），这样可以使节点 a 和节点 b 处于同一深度。
2. 寻找最近公共祖先：
   • if (a == b) return a;：如果此时 a 和 b 相等，说明已经找到了最近公共祖先，直接返回 a。
   • 再次通过循环 for (int k = 15; k >= 0; k -- )，从 2^15 级祖先开始，若节点 a 和节点 b 的 2^k 级祖先不相等，则将节点 a 和节点 b 同时向上提升到它们的 2^k 级祖先（a = fa[a][k]; b = fa[b][k];）。
   • 循环结束后，a 和 b 的父节点（即 fa[a][0]）就是它们的最近公共祖先，返回 fa[a][0]。

（五）main 函数

int main()
{
    scanf("%d", &n);
    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);

    scanf("%d", &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }

    return 0;
}

1. 输入图的信息：
   • scanf("%d", &n);：读取输入的边的数量 n。
   • int root = 0;：初始化根节点为 0。
   • memset(h, -1, sizeof h);：将邻接表头数组 h 初始化为 -1，表示每个节点的第一条边还未添加。
   • 通过循环 for (int i = 0; i < n; i ++ ) 读取每条边的两个端点 a 和 b：
     • 如果 b == -1，则将 a 设为根节点（root = a;）。
     • 否则，通过 add(a, b), add(b, a); 在邻接表中添加双向边。
2. 计算节点深度和祖先关系：
   • bfs(root);：以确定的根节点 root 为起点，调用 bfs 函数进行广度优先搜索，计算每个节点的深度和各级祖先。
3. 处理查询：
   • scanf("%d", &m);：读取查询的次数 m。
   • 通过循环 while (m -- ) 处理每个查询：
     • 读取两个节点 a 和 b（scanf("%d%d", &a, &b);）。
     • 调用 lca(a, b) 函数计算它们的最近公共祖先 p。
     • 根据 p 与 a、b 的关系进行输出：如果 p == a，输出 1；如果 p == b，输出 2；否则输出 0。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 图的构建：添加 n 条边，每次添加边的操作时间复杂度为 (O(1))，所以构建图的时间复杂度为 (O(n))。
2. BFS 过程：每个节点最多入队和出队一次，每条边最多被访问两次，时间复杂度为 (O(n + m’))（这里的 (m’) 是实际的边数，由于是无向图，实际输入的 n 就是边数，即 (m’ = n)，所以时间复杂度为 (O(n))）。
3. 计算最近公共祖先：每次查询时，通过两次循环，每次循环最多执行 16 次（因为 k 从 15 到 0），有 m 次查询，所以计算最近公共祖先的时间复杂度为 (O(m \times 2 \times 16) = O(m))（这里忽略常数项）。
   • 总体时间复杂度为 (O(n + m))。

（二）空间复杂度

1. 邻接表存储图结构：边的数量最多为 (M = N \times 2)，节点的数量为 (N)，所以邻接表的空间复杂度为 (O(N + M) = O(N))（因为 (M = 2N)）。
2. 存储深度和祖先信息：depth[N] 数组占用 (O(N)) 的空间，fa[N][16] 数组占用 (O(N \times 16) = O(N)) 的空间。
3. 队列 q[N]：占用 (O(N)) 的空间。
   • 总体空间复杂度为 (O(N))。