我不知道如何确定有向图是否具有GET-卡住顶点，这与度的n-1和出度0定义为一个顶点。
我想哑的方法是将打印在度和出度图中的每个顶点的，但是这是O（M + N）。 我感兴趣的是一个O（n）的算法。 有任何想法吗？
谢谢！！
Answer 1:
（I假设n为顶点和m是边缘。）
请注意，是在一个图表最多一个GET-卡住顶点。
假设我们有一个O（n）的算法。 如果m大，我们必须得出结论，而不考虑逢缘。
如果我们认为一开始卡住顶点存在，我们声称没有未考虑边缘导致了它，这是我们无法知道。
因此，我不认为O（n）是可能的。
O（M）是相当简单的。
Answer 2:
我同意测试版，有没有办法可以解决由O（N）这个问题，因为你必须访问每个边至少一次，以验证它是否是一个GET粘连节点。
文章来源: Graph theory algorithm to find vertex with out-degree 0 and in-degree (n-1)
标签：
graph-theory
