[原创+翻译]《算法导论（第二版）》Exer. 22.1-6：图的通用汇点（Universal Sink）

问题

如果我们使用邻接矩阵来表示图，则大多数用于解决图相关问题的算法的时间复杂度都为Ω(|V|²)，其中V代表图中的顶点集合。然而，并非所有情况都如此。例如，在给定一个有向图G及其邻接矩阵A的情况下，请提供一种能够在Ο(|V|)时间内判断该图G是否存在一个通用汇点（即入度为|V|-1且出度为0的顶点）的方法。

思路

如果矩阵元素A[i,j]等于1，则表示(i,j)属于边集E（其中1\leq i \leq |V|且1\leq j \leq |V|），因此顶点i无法成为通用汇点的原因是有出边的存在。由此可知，在这种情况下（即当某行存在元素为1时），对应的顶点i就不是通用汇点这一事实成立的原因是有出边的存在。另一方面，在这种情形下（即当某顶点不存在自循环边时），若该顶点有自循环边，则它同样无法成为通用汇点这一结论也是成立的。现在假设矩阵元素A[i,j]等于0，则表示(i,j)不属于边集E且i\neq j的情况下（即同一顶点之间不存在连接），则该情况表明：要么该顶点j的入度严格小于图中总顶点数减一（即|V|-1），要么它拥有自循环边的存在这一事实同样成立的情况下，则该顶点j也无法成为通用汇点这一结论同样成立。因此，在这种情况下（即当某列所有非对角线位置上的值均为0时），对应的顶点j同样无法成为通用汇点这一结论也成