题解：电力问题

一、题目背景

给定一个由 (n) 个点 (m) 条边构成的无向图，要求求出删除图中的一个点之后，图中连通块最多的数量。输入包含多组数据，以“(0 0)”作为输入结束标志。

二、解题思路

本题可通过Tarjan算法找出图中的割点（关节点），计算删除每个点后连通块增加的数量，从而得到删除一个点后最多的连通块数量。割点是指删除该点后，图的连通分量数量增加的点。对于每个点，通过Tarjan算法遍历其邻接子树，统计子树中满足特定条件（子树节点无法回溯到当前点的祖先）的子树数量，再结合图中原本的连通分量情况，计算出删除该点后的连通块数量。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、时间戳数组 dfn[N]（记录节点首次访问的时间戳）、追溯数组 low[N]（记录节点或其子孙能追溯到的最早时间戳）、当前遍历的根节点 root、答案变量 ans。
2. 编写添加边的函数 add，用于构建邻接表。
3. 实现Tarjan算法函数 tarjan，用于找出删除某个点后增加的连通块数量：
- 更新当前节点的 dfn 和 low 值。
- 遍历当前节点的邻接边，对于未访问的节点，递归调用 tarjan 并更新 low 值，若发现子树节点无法回溯到当前点的祖先（low[j] >= dfn[u]），则连通块数量 cnt 加 (1)。
- 对于已访问的节点，更新 low 值。
- 若当前节点不是根节点，将 cnt 加 (1)（因为删除当前节点后，当前节点与父节点所在部分会分开）。
- 更新答案 ans 为 ans 和 cnt 中的较大值。
4. 在 main 函数中：
- 循环读取输入，直到输入为“(0 0)”。
- 每次输入新数据前，初始化相关数组和变量。
- 读取每条边，构建图的邻接表。
- 初始化答案 ans 和图中连通分量数量 cnt。
- 遍历每个节点作为根节点调用 tarjan 算法，统计图中原本的连通分量数量。
- 输出删除一个点后最多的连通块数量，计算公式为 ans + cnt - 1（cnt - 1 是因为原本的连通分量在删除点后会被分割，需要减去重复计算的部分）。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

const int N = 10010, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root, ans;

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 10010, M = 30010;：定义节点的最大数量和边的最大数量。
3. 变量定义：
   • int n, m;：分别表示图中节点的数量和边的数量。
   • int h[N], e[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int dfn[N], low[N], timestamp;：dfn[N] 记录节点首次访问的时间戳，low[N] 记录节点或其子孙能追溯到的最早时间戳，timestamp 是时间戳计数器。
   • int root, ans;：root 表示当前遍历的根节点，ans 用于记录删除一个点后最多的连通块数量。

（二）添加边函数

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

该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点。通过更新邻接表数组，将边的信息存储起来。

（三）Tarjan算法函数

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;

    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) cnt ++ ;
        }
        else low[u] = min(low[u], dfn[j]);
    }

    if (u != root) cnt ++ ;

    ans = max(ans, cnt);
}

1. 初始化当前节点的 dfn 和 low 值为当前时间戳。
2. 初始化连通块数量 cnt 为 (0)，遍历当前节点的邻接边：
   • 若邻接节点未访问，递归调用 tarjan 函数，并更新当前节点的 low 值，若发现子树节点无法回溯到当前点的祖先（low[j] >= dfn[u]），则连通块数量 cnt 加 (1)。
   • 若邻接节点已访问，更新当前节点的 low 值为当前 low 值和邻接节点 dfn 值的较小值。
3. 若当前节点不是根节点，将 cnt 加 (1)（因为删除当前节点后，当前节点与父节点所在部分会分开）。
4. 更新答案 ans 为 ans 和 cnt 中的较大值。

（四）main 函数

int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        memset(dfn, 0, sizeof dfn);
        memset(h, -1, sizeof h);
        idx = timestamp = 0;

        while (m -- )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }

        ans = 0;
        int cnt = 0;
        for (root = 0; root < n; root ++ )
            if (!dfn[root])
            {
                cnt ++ ;
                tarjan(root);
            }

        printf("%d\n", ans + cnt - 1);
    }

    return 0;
}

1. 循环读取输入的节点数量 n 和边数量 m，直到输入为“(0 0)”。
2. 每次输入新数据前，初始化 dfn 数组（清零）、邻接表（h 数组设为 (-1)）、边编号 idx 和时间戳 timestamp。
3. 读取每条边，构建图的邻接表。
4. 初始化答案 ans 为 (0)，图中连通分量数量 cnt 为 (0)。
5. 遍历每个节点作为根节点：
   • 若节点未访问，说明是一个新的连通分量，cnt 加 (1)，并调用 tarjan 算法。
6. 输出删除一个点后最多的连通块数量，计算公式为 ans + cnt - 1。
7. 程序结束。

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

（一）时间复杂度

1. 建图：读取 (m) 条边构建邻接表，时间复杂度为 (O(m))。
2. Tarjan算法：对于每个节点最多访问一次，每条边最多遍历一次，每次调用 tarjan 函数的时间复杂度为 (O(n + m))，总共调用 (n) 次（每个节点都可能作为根节点），但由于图是连通的，实际时间复杂度仍为 (O(n + m))。
   总体时间复杂度为 (O(n + m))。

（二）空间复杂度

1. 邻接表：存储边的信息，空间复杂度为 (O(m))。
2. 其他数组：时间戳数组 dfn[N]、追溯数组 low[N] 等，空间复杂度为 (O(n))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。