我有一个图和一个起始节点。我想找出当我使用DFS删除图中的每个节点时，有多少节点被隔离。
例如，如果我从一个固定的节点1开始，并移除节点2，我将有多少个孤立的节点?如果我移除节点3呢?
我知道我可以为所有节点做DFS(每次删除一个不同的节点)，但这样做我将不得不为每个节点导航一次图，我想只用一次运行来解决它。
我被告知它有O(|V|*||A|)，其中|V|=边数，而|A|=节点数。
我一直在玩prenum和postnums，但没有成功。
设N为顶点数，M为边数。如果你只是想要一个0 (NM)的解决方案，你只需要为每个顶点运行一个DFS。
每个DFS的复杂度为O(N+M)，因此总复杂度为O(N(N+M)) = O(N²+NM)。通常我们的边比顶点多，所以NM的增长速度比N²快得多我们可以说复杂度是0 (NM)但是要记住，如果你在每一步都物理地删除当前顶点，你的实现将会有更糟糕的复杂性，因为物理地删除顶点意味着从大量邻接表中删除条目，无论你如何表示图，这都是昂贵的。有一个实现技巧可以加速这个过程:在每次DFS之前，不是物理地删除当前顶点，而是将顶点标记为已删除，当你在DFS期间遍历邻接表时，只需忽略标记的顶点。
然而，我觉得你可以在O(N+M)内解决这个问题，使用Tarjan的算法来寻找结合点。该算法将找到每个顶点，当从图中删除时，将图分割为多个连接组件(这些顶点称为衔接点)。很容易看出，如果你移除一个不是连接点的顶点，就不会有孤立的顶点。然而，如果你移除一个连接点，你将把图分成两个部分G和G'，其中G是起始顶点的连接部分，而G'是图的其余部分。G'中的所有顶点都是孤立的，因为如果从起始顶点运行DFS，就无法到达它们。我认为你可以有效地找到G'的大小对于每个顶点的删除，也许你甚至可以在运行Tarjan的时候做这个。如果我找到一个解决方案，我可以稍后编辑这个答案。
编辑:我设法在0 (N+M)内解决了这个问题。我会给一些提示，这样你就可以自己找到答案了:每个无向图都可以被分解成(不是不相交的)双连通分量集:每个双连通分量是图的顶点的一个子集，即使你删除了图的任何顶点，这个子集中的每个顶点都将保持连接
Tarjan的O(N+M)算法用于寻找桥梁和连接点，可以改变以找到双连接组件，找出哪些顶点属于每个双连接组件，或者哪些双连接组件包含每个顶点
如果你删除任何不是接合点的顶点，这个顶点的答案显然是N-1
如果你移除一个连接点，起始顶点的相同双连接组件中的每个顶点仍然是可访问的，但你不知道其他双连接组件。别担心，有一种方法可以有效地找到它
你可以压缩图B中每一个双连通分量的图G。压缩算法很简单:每个双连接组件都成为B中的一个顶点，然后将共享某个连接点的双连接组件连接起来。我们可以证明结果图B是树。为了解决步骤4中出现的问题，必须使用此树
祝你好运!