10得票7回答
图论:在不超过O(|V|)的时间内找到汇点 - 或者证明无法完成

我有一个包含n个节点的邻接矩阵图。 是否可能在少于O(n)时间内检测出汇点(sink)? 如果可以,该如何检测?如果不行,如何证明? 汇点顶点是一条入边均来自其他节点而没有出边的顶点。