给定图G与顶点子集A的符合条件子集B、C高效算法设计

问题重述 #

给定有向图G和顶点子集A，判断是否存在顶点集V的两个子集B、C满足三个条件：

1. B∩C ⊆ A
2. B中每个顶点都存在至少一条可到达A中某一顶点的路径
3. C中每个顶点都可被A中至少一个顶点到达

思路校验 #

你给出的核心思路是完全正确的，只有少量伪代码细节需要修正：

• 原伪代码中未初始化的c3变量冗余，直接判断顶点是否属于A即可，不需要单独的颜色标记
• A中顶点遍历启动条件不需要额外判断颜色，直接从所有A中顶点启动遍历即可
• 你提到的两种遍历逻辑是对的：
  • 转置图（所有边反向的图）上从A出发DFS，能访问到的所有点就是原图中可以到达A的顶点，刚好是B的可选范围
  • 原图上从A出发DFS，能访问到的所有点就是可以被A到达的顶点，刚好是C的可选范围

要满足B∩C⊆A的核心约束，等价于上述两个遍历结果的交集不能包含A之外的顶点：如果存在A之外的顶点同时在两个遍历结果里，说明该点既能到达A、也能被A到达，不管怎么选B、C，只要要覆盖所有符合可达条件的顶点，都会出现交集超出A的情况，因此不存在符合要求的集合。

修正后的中文伪代码 #

Algo(G, A)
    B = 空集
    C = 空集
    // c1标记转置图遍历状态，c2标记原图遍历状态，B=未访问，N=已访问
    初始化颜色数组c1、c2
    Gt = 转置图(G)

    // 初始化颜色：A中顶点默认属于B和C，标记为已访问
    对每个v ∈ 顶点集V:
        c1[v] = c2[v] = B
    对每个a ∈ A:
        c1[a] = c2[a] = N

    // 从A的所有顶点启动遍历
    对每个a ∈ A:
        DFS_Visit(Gt, a, c1)
        DFS_Visit(G, a, c2)

    // 收集B、C集合
    对每个v ∈ V:
        如果 c1[v] == N:
            B.add(v)
        如果 c2[v] == N:
            C.add(v)

    // 校验交集约束
    对每个v ∈ V:
        如果 c1[v] == N 且 c2[v] == N 且 v ∉ A:
            打印 "不存在符合要求的B、C集合"
            返回 false

    输出B、C集合
    返回 true

效率说明 #

该算法时间复杂度为O(V+E)，属于线性时间复杂度的最优解法，遍历和转置图生成都只需要遍历一次所有顶点和边，适合处理大规模有向图场景。

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