有向图中互相可达顶点的中间点是否必属同一强连通分量(SCC)

结论：是的，这些中间顶点必然与A、B属于同一个强连通分量

核心分析 #

根据强连通分量（SCC）的定义：强连通分量是有向图中最大的顶点子集，其中任意两个顶点之间都存在双向可达的路径。

针对题目场景：

• 已知A与B互相可达，即存在路径A → ... → B和B → ... → A。
• 对于路径上的任意中间顶点X（比如C、D、E）：
  1. A可以通过路径的前半段到达X；
  2. X可以通过路径的后半段到达B，而B又能到达A，因此X可以顺着X → ... → B → ... → A的路径到达A；
  3. 这就满足了A与X互相可达的条件，因此X必然和A、B同属一个强连通分量。

示例验证 #

针对你提到的具体场景：A直接连接B，B通过C、D、E连接A（路径为A→B和B→C→D→E→A）：

• A能通过A→B→C到达C，C能通过C→D→E→A到达A，双向可达；
• 同理，D、E都能与A、B形成双向可达路径，因此所有顶点必然属于同一个强连通分量。

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