由网友(宇宙无敌超级霹雳小仙女)分享简介：给定一个图，我们怎样才能判断是否存在一个顶点v，使所有其它顶点可达。该算法应该是尽可能高效Given a graph, how can we determine whether or not there exists a vertex v, from which all other vertices are reac...

给定一个图，我们怎样才能判断是否存在一个顶点v，使所有其它顶点可达。该算法应该是尽可能高效

Given a graph, how can we determine whether or not there exists a vertex v, from which all other vertices are reachable. the algorithm should be as efficient as possible.

我知道如何做到这一点，如果我们检查一个给定的顶点;我们可以做相反的图形DFS。但对于这个问题，似乎低效这样做对图中的每一个顶点。

I know how to do it if we are checking for a given vertex; we could do dfs on the reverse graph. But for this question, it seems inefficient to do it for every vertex in the graph.

有没有更好的办法？

感谢。

推荐答案

使用的Tarjan算法找到强烈该图在时间的连接组件 O（| V | + | E |）。如果你再缩水每个组件到一个节点，你会留下一个向无环图。存在一个顶点从所有其他人可以当且仅当恰好有一个顶点在DAG与度0。这是你要找的顶点到达 - 即所谓的母亲顶点

Use Tarjan's algorithm to find the strongly connected components of the graph in time O(|V|+|E|). If you then "shrink" each component to a single node, you'll be left with a directed acyclic graph. There exists a vertex from which all others can be reached if and only if there is exactly one vertex in the DAG with in-degree 0. This is the vertex you're looking for - the so-called "mother vertex".