证明近强连通有向图中存在可到达所有顶点的顶点

首先先明确题目里的核心定义，避免歧义：

核心定义回顾 #

• 强连通分量图 $G^{SCC}$：给定有向图 $G=(V,E)$，其顶点集为所有 $G$ 的强连通分量构成的集合 $V^{SCC}={C\mid C是G的强连通分量}$，边集为 $E^{SCC}={(C_i,C_j)\mid \exists(u,v)\in E且u\in C_i, v\in C_j}$。强连通分量图的关键性质是它一定是有向无环图（DAG）。
• 近强连通有向图：若对任意顶点对 $s,t\in V$，要么存在从 $s$ 到 $t$ 的路径，要么存在从 $t$ 到 $s$ 的路径，则称 $G$ 是近强连通的。

我们要证明的结论是：若 $G$ 是近强连通的，则存在某个顶点 $v\in V$，使得图中所有顶点都可从 $v$ 到达。

证明过程 #

步骤1：分析强连通分量图 $G^{SCC}$ 的性质 #

因为 $G$ 是近强连通的，所以它的强连通分量图 $G^{SCC}$ 也必然是近强连通的——原因很简单：任取两个分量 $C_i,C_j\in V^{SCC}$，取 $u\in C_i$、$v\in C_j$，根据 $G$ 的近强连通性，要么 $u$ 能到 $v$（对应 $C_i$ 到 $C_j$ 有路径），要么 $v$ 能到 $u$（对应 $C_j$ 到 $C_i$ 有路径），完全符合近强连通的定义。

而 $G^{SCC}$ 是DAG，DAG的近强连通性意味着它必须是全序的：所有分量可以排成一个线性序列 $C_1, C_2, ..., C_k$，其中对任意 $1\leq i<j\leq k$，存在从 $C_i$ 到 $C_j$ 的路径（反过来不可能，否则会形成环，违反DAG的定义）。

为什么不能有两个“不可互达”的分量？假设存在 $C_a$ 和 $C_b$，两者之间没有任何方向的路径，那取 $u\in C_a$、$v\in C_b$，就会出现既没有 $u$ 到 $v$ 的路径，也没有 $v$ 到 $u$ 的路径，直接和 $G$ 的近强连通性矛盾。所以 $G^{SCC}$ 一定是一条线性的可达链。

步骤2：找到关键的强连通分量 #

在这个线性可达链 $C_1 \to C_2 \to ... \to C_k$ 中，最靠前的分量 $C_1$ 是唯一的源分量（入度为0的分量）——如果存在另一个源分量，那这两个源分量之间必然没有路径，又会回到刚才的矛盾。

对于这个源分量 $C_1$，根据链的性质，它可以到达后面所有的分量 $C_2,C_3,...,C_k$：因为对任意 $C_j$（$j>1$），要么 $C_1$ 到 $C_j$ 有路径，要么 $C_j$ 到 $C_1$ 有路径；但如果是后者，$C_1$ 就会有入度（来自 $C_j$ 的路径），和它是源分量的事实矛盾，所以只能是 $C_1$ 到 $C_j$ 有路径。

步骤3：验证分量内的顶点满足条件 #

因为 $C_1$ 是强连通分量，所以 $C_1$ 内的任意一个顶点 $v$，都能到达 $C_1$ 里的所有顶点；同时，由于 $C_1$ 能到达所有其他分量，$v$ 也能到达其他分量里的所有顶点。

综上，$v$ 就是那个可以到达图中所有顶点的顶点。

补充：反证法思路（可选） #

如果觉得正向推导不够直观，咱们用反证法再验证一遍：
假设不存在这样的顶点，即对每个顶点 $x$，都存在至少一个顶点 $y_x$ 使得 $x$ 无法到达 $y_x$。根据近强连通性，$y_x$ 一定能到达 $x$。

现在构造顶点序列：取 $v_1$，找到 $v_2$ 使得 $v_1$ 到不了 $v_2$ 但 $v_2$ 能到 $v_1$；再取 $v_2$，找到 $v_3$ 使得 $v_2$ 到不了 $v_3$ 但 $v_3$ 能到 $v_2$……以此类推。

因为顶点总数是有限的，这个序列必然会出现重复，比如 $v_m = v_n$（$m<n$），这就形成了一个环：$v_m \leftarrow v_{m+1} \leftarrow ... \leftarrow v_n = v_m$，意味着这些顶点都属于同一个强连通分量，但根据构造，$v_m$ 到不了 $v_{m+1}$，这和强连通分量“任意顶点互相可达”的定义矛盾。所以假设不成立，必然存在这样的顶点。

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