AcWing 2752. 仙人掌图 题解

题目分析

本题给定一个无向连通图，要求判断是否为仙人掌图（任意一条边至多只出现在一条简单回路里），并在确定是仙人掌图的情况下，求出图的直径（图上相距最远的两个点的距离，边权都为1）。输入数据以路径的形式给出图的边信息。

解题思路

本题通过Tarjan算法找出图中的环，将仙人掌图转化为类似树的结构（把环缩成一个点），然后在这个类似树的结构上进行深度优先搜索来计算图的直径。
1. 图的存储与初始化：使用邻接表存储图，h1用于存储原始图，h2用于存储转化后的类似树的结构。add函数用于向邻接表中添加边。
2. 寻找环并转化图结构：tarjan函数利用Tarjan算法找出图中的环，对于不在环上的边直接添加到新图h2中；对于环上的边，通过build_circle函数重新构建环在新图中的连接方式，将环缩成一个虚拟点，环上的点与虚拟点相连，边权根据环上的距离计算。
3. 深度优先搜索计算直径：dfs函数对转化后的树进行深度优先搜索。对于每个节点，计算从该节点出发的最长和次长路径长度d1和d2。如果节点是原图中的点（非虚拟点），则更新答案为d1 + d2；如果节点是虚拟点，通过处理环上的路径信息，利用单调队列优化来计算经过该虚拟点的最长路径，进而更新答案。
4. 主函数处理输入输出：读入节点数、路径数和路径信息，构建原始图的邻接表。调用tarjan函数转化图结构，再调用dfs函数计算直径，最后输出结果。

代码逐段分析

1. 头文件和全局变量定义

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

using namespace std;

const int N = 100010, M = N * 3, INF = 1e8;

int n, m, new_n;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
int dfn[N], low[N], cnt;
int s[N], stot[N], fu[N], fw[N];
int d[N], f[N], q[N];
int ans;

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义常量N表示节点的最大数量，M表示边的最大数量，INF表示一个极大值。
• 变量n表示节点数，m表示路径数，new_n用于记录新图中节点的数量（包括虚拟节点）。
• h1[N]和h2[N]是邻接表的头指针数组，e[M]存储边的另一端节点，w[M]存储边的权值，ne[M]指向下一条边的下标，idx用于记录边的编号。
• dfn[N]和low[N]用于Tarjan算法中记录节点的访问顺序和最早能回溯到的祖先节点的访问顺序，cnt用于计数。
• s[N]用于记录环上节点到环上某一点的距离，stot[N]用于记录环上节点到环上起点的总距离，fu[N]记录节点的父节点，fw[N]记录从父节点到当前节点的边权。
• d[N]、f[N]和q[N]用于深度优先搜索过程中的辅助数组，d[N]存储一些距离信息，f[N]存储从节点出发的最长路径长度，q[N]用于单调队列。

• ans用于存储图的直径。

• 添加边函数

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

• 该函数用于向邻接表h中添加一条从节点a到节点b，权值为c的边。

• 构建环在新图中的结构函数

void build_circle(int x, int y, int z)
{
    int sum = z;
    for (int k = y; k != x; k = fu[k])
    {
        s[k] = sum;
        sum += fw[k];
    }
    s[x] = stot[x] = sum;
    add(h2, x, ++ new_n, 0);
    for (int k = y; k != x; k = fu[k])
    {
        stot[k] = sum;
        add(h2, new_n, k, min(s[k], sum - s[k]));
    }
}

• 该函数用于处理环上的边，将环缩成一个虚拟点。
• 首先计算环上节点到环上某一点的距离sum，并记录在s[k]中。
• 添加一个新的虚拟点new_n，将环上的起点x与虚拟点相连，边权为0。

• 然后将环上其他节点与虚拟点相连，边权为该节点到环上起点的最短路径距离（通过min(s[k], sum - s[k])计算）。

• Tarjan算法函数

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ cnt;
    for (int i = h1[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            fu[j] = u, fw[j] = w[i];
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) add(h2, u, j, w[i]);
        }
        else if (i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }
    for (int i = h1[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dfn[u] < dfn[j] && fu[j] != u)
            build_circle(u, j, w[i]);
    }
}

• 该函数使用Tarjan算法找出图中的环。
• 初始化节点u的访问顺序dfn[u]和最早能回溯到的祖先节点的访问顺序low[u]。
• 遍历节点u的所有邻边：
  • 如果邻接节点j未被访问，记录其父节点和边权，递归调用tarjan函数，并更新low[u]。如果dfn[u] < low[j]，说明这条边不在环上，将其添加到新图h2中。
  • 如果邻接节点j已被访问且不是从父节点过来的边，则更新low[u]。

• 再次遍历节点u的邻边，对于环上的边（根据dfn[u] < dfn[j]和fu[j] != u判断），调用build_circle函数处理环。

• 深度优先搜索函数

int dfs(int u)
{
    int d1 = 0, d2 = 0;
    for (int i = h2[u]; ~i; i = ne[i])
    {
        int j = e[i];
        int t = dfs(j) + w[i];
        if (t >= d1) d2 = d1, d1 = t;
        else if (t > d2) d2 = t;
    }
    f[u] = d1;
    if (u <= n) ans = max(ans, d1 + d2);  
    else  
    {
        int sz = 0;
        d[sz ++ ] = -INF;
        for (int i = h2[u]; ~i; i = ne[i])
            d[sz ++ ] = f[e[i]];
        for (int i = 0; i < sz; i ++ ) d[sz + i] = d[i];

        int hh = 0, tt = -1;
        for (int i = 0; i < sz * 2; i ++ )
        {
            if (hh <= tt && i - q[hh] > sz / 2) hh ++ ;
            if (hh <= tt) ans = max(ans, d[i] + i + d[q[hh]] - q[hh]);
            while (hh <= tt && d[q[tt]] - q[tt] <= d[i] - i) tt -- ;
            q[ ++ tt] = i;
        }
    }

    return f[u];
}

• 该函数对转化后的树进行深度优先搜索，计算从每个节点出发的最长路径，并更新图的直径。
• 对于每个节点u，先初始化最长和次长路径长度d1和d2。
• 遍历节点u的所有邻边，递归计算邻接节点的最长路径并加上边权，更新d1和d2。
• 将d1赋值给f[u]。
• 如果节点u是原图中的点（u <= n），则更新答案ans为d1 + d2。
• 如果节点u是虚拟点：
  • 先将-INF存入d[0]，然后将从虚拟点出发的各条路径的最长长度存入d数组，并将数组复制一份拼接在后面。
  • 使用单调队列（q数组）优化计算经过该虚拟点的最长路径，更新答案ans。

• 最后返回从节点u出发的最长路径长度f[u]。

• 主函数

int main()
{
    scanf("%d%d", &n, &m);
    new_n = n;
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);
    while (m -- )
    {
        int k, x, y;
        scanf("%d%d", &k, &x);
        for (int i = 0; i < k - 1; i ++ )
        {
            scanf("%d", &y);
            add(h1, x, y, 1), add(h1, y, x, 1);
            x = y;
        }
    }
    tarjan(1, -1);
    dfs(1);

    printf("%d\n", ans);
    return 0;
}

• 读入节点数n和路径数m，初始化新图节点数new_n和邻接表头指针数组。
• 读入路径信息，构建原始图的邻接表。
• 调用tarjan函数找出图中的环并构建新图结构。
• 调用dfs函数计算图的直径。
• 输出图的直径ans。

时间复杂度分析

• Tarjan算法的时间复杂度为(O(M + N))，其中(M)是边数，(N)是节点数。
• 深度优先搜索的时间复杂度为(O(N + M))，在处理虚拟点时使用单调队列，每次操作时间复杂度为(O(1))，总的时间开销仍在(O(N + M))量级。
• 总体时间复杂度为(O(N + M))。

空间复杂度分析

主要空间消耗在于邻接表、各种辅助数组等，空间复杂度为(O(N + M)) 。