我有一個圖形和一個起始節點。當我使用DFS刪除圖中的所有節點的每個節點時，我想查找有多少節點變得孤立。DFS計算關節點的隔離節點
例如，如果我從固定節點1開始，並刪除節點2，我將擁有多少個隔離節點？如果我刪除節點3？
我知道我可以爲所有節點做DFS（每次移除一個不同的節點），但是這樣做，我將不得不爲每個節點導航一次圖形，我想用一次運行來解決它。我已經被告知它有O（| V | * || A |），其中| V | =邊的數量，並且| A | =節點的數量。
我一直在玩prenum和postnums，但沒有成功。
設N是頂點的數量，M是邊的數量。如果您只需要一個O（NM）解決方案，您就不需要爲每個頂點運行DFS。每個DFS的複雜度爲O（N + M），因此總複雜度爲O（N（N + M））= O（N 2 + NM）。通常我們有更多的邊緣比頂點，所以NM增長得比N²快得多，我們可以說複雜度是O（NM）。但請記住，如果您在每一步中物理刪除當前頂點，則實現的複雜性會更差，因爲物理刪除頂點意味着從大量鄰接列表中刪除條目，無論您如何表示圖形。有一個實現技巧可以加速該過程：不是在每個DFS之前物理刪除當前頂點，只需將頂點標記爲已刪除，並且在DFS期間通過鄰接列表時忽略標記的頂點。
但是，我覺得你可以在O（N + M）中使用Tarjan算法解決這個問題，以找到關節點。該算法將查找從圖中刪除的每個頂點，將圖分成多個連接的組件（這些頂點稱爲關節點）。很容易看出，如果刪除不是關節點的頂點，則不會出現孤立的頂點。但是，如果刪除關節點，則將圖形分爲G和G'兩部分，其中G是起始頂點的連通部分，G'是圖形的其餘部分。 G'中的所有頂點都是孤立的，因爲如果從起始頂點運行DFS，則無法到達頂點。我認爲你可以高效地找到每個頂點刪除的G'的大小，也許你甚至可以在運行Tarjan的時候這樣做。如果我找到解決方案，我可以稍後編輯此答案。
編輯：我設法解決O（N + M）中的問題。我會給出一些提示，這樣你可以找到自己的答案：
每一個無向圖可以（不相交）套雙連通組件的分解：每個雙連通分量的圖，其中的頂點的一個子集即使刪除圖的任何頂點，該子集中的每個頂點都將保持連接
找到橋樑和關節點的Tarjan的O（N + M）算法可以改變以找到雙連通的組件，找到哪些頂點屬於每個雙連通分量，或雙連通部件包含每個頂點
如果你刪除任何頂點這不是一個關節點，回答這個頂點顯然是N-1
如果刪除的鉸接點，在起始頂點相同的雙連通分量的每個頂點仍然會acessible，但你不知道其他的雙連通分支。別擔心，還有就是找到這個有效
你可以在它的雙連通分支的曲線B每壓縮圖G的方式。壓縮算法很簡單：每雙連通分量成爲B中的頂點，你鏈接分享一些關節點雙連通分支。我們可以證明結果圖B是一棵樹。您必須以某種方式使用此樹以解決步驟4中出現的問題。
祝您好運！
請提供一個具體的例子。 – Tempux