线性时间求解图中u到v所有路径均不经过且属于A的顶点Z

原实现的问题 #

你给出的基于Kosaraju算法的实现存在多处逻辑和功能缺陷：

• 未处理输入参数中的顶点数组A，直接返回全图符合条件的顶点，不符合题目要求输出A的子集的规则
• 直接修改原图邻接表新增u和v的双向边，会产生额外副作用破坏原始图结构
• 存在变量名冲突（循环变量与输入参数v重名）、方法名拼写错误（traspose应为transpose）等编码bug
• 逻辑虽然近似符合判断条件，但实现复杂度远高于必要的线性算法，可读性和可维护性差

核心判定逻辑 #

我们要找的是所有不在任意一条u到v的路径上的顶点，等价于顶点z满足以下两个条件任意一个：

• u无法到达z
• z无法到达v

正确线性时间算法 #

整体时间复杂度为O(V+E)，完全满足线性要求，步骤如下：

1. 从u出发对原图做一次BFS/DFS，记录所有u可达的顶点集合reachable_from_u
2. 构建图的转置（所有边方向反转），从v出发对转置图做一次BFS/DFS，记录所有v可达的顶点集合can_reach_v，该集合等价于原图中所有能到达v的顶点
3. 遍历输入数组A，筛选出所有满足z not in reachable_from_u or z not in can_reach_v的顶点，组成结果集Z返回

示例实现代码 #

def algo(G: Graph, u: Node, v: Node, A: list[Node]) -> list[Node]:
    # 第一步：求u的可达集
    reachable_from_u = set()
    def dfs_u(node):
        if node in reachable_from_u:
            return
        reachable_from_u.add(node)
        for next_node in node.adjacenciesList:
            dfs_u(next_node)
    dfs_u(u)
    
    # 第二步：求能到达v的顶点集（转置图上v的可达集）
    Gt = G.transpose()
    can_reach_v = set()
    def dfs_v(node):
        if node in can_reach_v:
            return
        can_reach_v.add(node)
        for next_node in Gt.get_adjacencies(node):
            dfs_v(next_node)
    dfs_v(v)
    
    # 第三步：筛选A中符合条件的顶点
    Z = []
    for z in A:
        if z not in reachable_from_u or z not in can_reach_v:
            Z.append(z)
    return Z

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