C语言求解动态加边后火星城市战略道路计数的优化方案问询

你提到的「战略道路」就是图论中的割边（桥），你当前的暴力实现思路只适合极小数据量，一旦N、M规模超过1000就会出现明显的性能问题，有更高效的标准解法：

原方案缺陷 #

• 时间复杂度达到O(QM(M+N))，每次新增一条边后都遍历所有道路做连通性检测，完全无法承载中大规模输入
• 连通性检测中使用线性查找、频繁realloc都额外增加了运行开销
• 每次调用strategic函数分配的内存没有释放，存在内存泄漏问题

最优实现思路 #

整体时间复杂度可以控制在O(N + M + Q log N)，完全可以处理1e5级别的数据规模：

1. 初始计算：对原始图运行Tarjan割边算法，统计初始的桥的总数，同时将原图的每个边双连通分量（即没有桥的极大连通子图）缩为一个节点，缩点后得到的结构是一棵树，树上所有边都对应原图的桥。
2. 动态加边处理：每次新增一条连接u、v的道路时：
   • 找到u、v分别所属的边双连通分量在缩点树中的节点a、b
   • 找到a到b在缩点树上的路径，这条路径上的所有边都会因为新增的边形成环，不再是桥，直接从总桥数中减去路径上的边数
   • 将路径上的所有节点合并为同一个连通分量，后续不需要再处理这些边

核心代码参考（C语言兼容） #

首先是Tarjan找桥的核心逻辑：

#include <stdio.h>
#include <string.h>
#define MAXN 100005
#define MAXM 200005

int head[MAXN], tot;
int dfn[MAXN], low[MAXN], timestamp;
int bridge_cnt; // 初始桥的总数
int is_bridge[MAXM * 2];

struct Edge {
    int to, next;
} edge[MAXM * 2];

void add_edge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++timestamp;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = low[u] < low[v] ? low[u] : low[v];
            if (low[v] > dfn[u]) {
                is_bridge[i] = is_bridge[i ^ 1] = 1;
                bridge_cnt++;
            }
        } else if (i != (in_edge ^ 1)) {
            low[u] = low[u] < dfn[v] ? low[u] : dfn[v];
        }
    }
}

之后做边双缩点，再用带LCA的并查集处理每次加边的路径合并即可。

内容的提问来源于stack exchange，提问作者rain 183