带权重约束的图中最长唯一链求解技术问询

第一步：预处理构建符合条件的子图 #

先从原带权图中过滤掉所有权重不在目标区间内的边，得到仅包含合法边的子图G'，用邻接表存储（比邻接矩阵更适合大规模图的遍历与空间节省）。问题直接转化为在G'中寻找所有最长简单路径（顶点不重复的链）。

第二步：拆分连通分量并行处理 #

对G'做连通性拆分：

• 无向图：用并查集（Union-Find）算法快速找出所有极大连通子图；
• 有向图：用Kosaraju或Tarjan算法分解强连通分量，再处理每个分量的路径。

不同连通分量的路径完全独立，拆分后可逐个处理，避免全图遍历的高复杂度。

第三步：针对不同规模的连通分量选择算法 #

情况1：连通分量是DAG（有向无环图）

用拓扑排序+动态规划高效求解：

1. 对DAG做拓扑排序；
2. 从拓扑序的起点开始，对每个节点u，维护两个值：max_len[u]（以u结尾的最长路径长度）、paths[u]（所有以u结尾的最长路径集合）；
3. 遍历每个节点的邻接节点v，若max_len[u] + 1 > max_len[v]，则更新max_len[v]并重置paths[v]为paths[u]中所有路径加上v；若长度相等，则将paths[u]的路径追加到paths[v]；
4. 最后遍历所有节点的max_len，找到最大值，对应的paths集合就是所有最长路径。
   时间复杂度O(V+E)，完全适配大规模DAG。

情况2：小规模连通分量（节点数<50）

用回溯+剪枝：

1. 从每个节点出发，递归遍历邻接的未访问节点，记录当前路径；
2. 剪枝优化：若当前路径长度 + 剩余未访问节点的最大可能路径长度（可预先计算连通分量的直径作为上界）小于已知最长路径长度，直接终止当前分支；
3. 维护全局最长路径长度和对应的路径集合，每次找到更长路径时更新，长度相等时追加路径。

情况3：大规模连通分量（节点数≥50）

最长简单路径的长度通常等于连通分量的直径（图中任意两点间的最长距离）：

1. 无向图求直径：用两次BFS/DFS，第一次从任意节点s找到最远节点u，第二次从u找到最远节点v，u到v的路径长度就是直径；
2. 找出所有长度等于直径的简单路径：以直径的两个端点为起点，用深度优先搜索收集所有长度等于直径的路径，过程中标记已访问节点避免重复；
3. 若为有向图，可使用Floyd-Warshall算法预处理所有节点对的最长路径（时间复杂度O(V³)，仅适合V≤200的分量），或用启发式A*算法优先搜索可能的最长路径。

优化技巧 #

• 用位图（Bitmask）存储已访问节点，比数组或哈希表更快，适合小规模分量；
• 对无向图，搜索时可限制仅访问编号大于当前节点的邻接点，避免生成重复的反向路径（后续再补全反向路径即可）；
• 用哈希集合对路径去重（若存在重复路径的情况）。

内容的提问来源于stack exchange，提问作者Yuki.kuroshita