题目分析

本题是一个图论相关的问题。煤矿工地可看作由隧道连接挖煤点组成的无向图，矿主需要在某些挖煤点设立救援出口，确保无论哪个挖煤点坍塌，其他挖煤点的工人都有道路通向救援出口。需要计算至少设置几个救援出口以及不同最少救援出口的设置方案总数。

代码逐段分析

1. 头文件和全局变量

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

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;

- 引入必要的头文件，包括字符串处理、输入输出、算法和向量相关的头文件，并使用标准命名空间。
- 定义 `ULL` 为 `unsigned long long` 的别名，方便后续使用。
- 定义常量 `N` 和 `M` 分别表示挖煤点的最大数量和隧道的最大数量。
- `n` 表示挖煤点的实际数量，`m` 表示隧道的数量。
- `h[N]`、`e[M]`、`ne[M]` 和 `idx` 用于实现邻接表存储图结构。
- `dfn[N]` 记录节点的时间戳，`low[N]` 记录节点或其子孙能回溯到的最早祖先的时间戳，`timestamp` 是时间戳计数器。
- `stk[N]` 和 `top` 用于实现栈，辅助 Tarjan 算法。
- `dcc_cnt` 记录双连通分量的数量，`dcc[N]` 存储每个双连通分量中的节点。
- `cut[N]` 标记节点是否为割点。
- `root` 表示当前 Tarjan 算法的起始节点。

1. 添加边的函数 add(int a, int b)

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

该函数用于在邻接表中添加一条从节点 a 到节点 b 的边。

1. Tarjan 算法函数 tarjan(int u)

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

    if (u == root && h[u] == -1)
    {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    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 (dfn[u] <= low[j])
            {
                cnt++;
                if (u != root || cnt > 1) cut[u] = true;
                ++dcc_cnt;
                int y;
                do
                {
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else
            low[u] = min(low[u], dfn[j]);
    }
}

- 初始化节点 `u` 的时间戳 `dfn[u]` 和 `low[u]`，并将节点 `u` 入栈。
- 如果节点 `u` 是根节点且没有邻接边，说明该节点是一个独立的双连通分量，直接将其加入双连通分量集合中。
- 遍历节点 `u` 的所有邻接节点 `j`：
    - 如果节点 `j` 未被访问过，递归调用 `tarjan(j)`，更新 `low[u]`，并根据 `dfn[u]` 和 `low[j]` 的关系判断节点 `u` 是否为割点，同时划分双连通分量。
    - 如果节点 `j` 已被访问过，更新 `low[u]` 为 `low[u]` 和 `dfn[j]` 的较小值。

1. 主函数 main()

int main()
{
    int T = 1;
    while (cin >> m, m)
    {
        for (int i = 1; i <= dcc_cnt; i++) dcc[i].clear();
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(cut, 0, sizeof cut);

        while (m--)
        {
            int a, b;
            cin >> a >> b;
            n = max(n, a), n = max(n, b);
            add(a, b), add(b, a);
        }

        for (root = 1; root <= n; root++)
            if (!dfn[root])
                tarjan(root);

        int res = 0;
        ULL num = 1;
        for (int i = 1; i <= dcc_cnt; i++)
        {
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j++)
                if (cut[dcc[i][j]])
                    cnt++;

            if (cnt == 0)
            {
                if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                else
                    res++;
            }
            else if (cnt == 1) res++, num *= dcc[i].size() - 1;
        }

        printf("Case %d: %d %llu\n", T++, res, num);
    }

    return 0;
}

- 初始化测试用例编号 `T` 为 1。
- 循环读取输入，直到输入的隧道数量 `m` 为 0。
- 每次处理新的测试用例前，清空双连通分量集合，重置各种变量和数组。
- 读取每条隧道连接的两个挖煤点，更新挖煤点的最大编号 `n`，并在邻接表中添加双向边。
- 对每个未被访问过的挖煤点调用 `tarjan` 算法，找出图中的所有双连通分量。
- 遍历每个双连通分量：
    - 统计双连通分量中割点的数量 `cnt`。
    - 根据 `cnt` 的值计算至少需要设置的救援出口数量 `res` 和设置方案总数 `num`。
- 输出结果，包括测试用例编号、至少需要设置的救援出口数量和设置方案总数。

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

• 时间复杂度：
  • 图的构建过程，每次添加边的操作时间复杂度为 (O(1))，共添加 (m) 条边，所以时间复杂度为 (O(m))。
  • Tarjan 算法遍历图的每个节点和边，时间复杂度为 (O(n + m))。
  • 后续处理双连通分量的时间复杂度为 (O(dcc_cnt \times max_size_of_dcc))，其中 (dcc_cnt) 是双连通分量的数量，(max_size_of_dcc) 是最大的双连通分量的大小，由于 (dcc_cnt \leq n)，(max_size_of_dcc \leq n)，所以这部分时间复杂度为 (O(n^2))。
  • 总体时间复杂度为 (O(n^2))。
• 空间复杂度：
  • 邻接表存储图结构，空间复杂度为 (O(n + m))。
  • 存储双连通分量和其他辅助数组的空间复杂度为 (O(n))。
  • 总体空间复杂度为 (O(n + m))。