在Taljan的實現中重複出現的鉸接點

Question

我最近學會了線性時間算法來計算圖形中的鉸接點。我的實現在Online Judge測試數據上正確運行，所以代碼沒有問題。然而，我似乎很難在DFS運行中發現多於一個的相同關節點。讓我解釋一下

我有一個列表，如果遇到關節點存儲。現在，當我最終打印列表時，我會得到正確的關節點，但是關節點的幾個頂點會出現多次。據我所知，這不應該發生，因爲我們只遇到每個頂點一次。那麼爲什麼我會重複列表中的條目？爲了解決這個問題，我在我的原始代碼中使用了一個HashSet來存儲它們，並在最後輸出正確答案的內容。這是我的問題代碼。該算法主要是基於關閉維基百科上的僞代碼這裏：https://en.wikipedia.org/wiki/Biconnected_component

這裏是我在C implmentation ++代碼：

/*input 
7 6 
0 1 
1 2 
3 4 
2 4 
2 6 
5 2 
*/ 
#include <bits/stdc++.h> 
using namespace std; 
#define endl '\n' 
#define pb emplace_back 
#define sz 3005 //In the current scenario, I need only a maximum on 3000 vertices 

typedef long long int ll; 

//Created by Shreyans Sheth [bholagabbar] 

bool visited [sz]; //whether the node has been discoverd in the DFS run or not 
int low [sz]; //time of the earliest discovered vertex reachable from the vertex 
int disc [sz]; //time at which vertex was explored 
int parent [sz]; //stores the parents of each vertex 
vector<int> a[sz]; //Adjacency List for graph 
int rtime; //Time 
vector<int> ap; //Stored the articulation points 

void DFS(int s) 
{ 
    visited[s]=1; 
    low[s]=disc[s]=++rtime; 
    int nchild=0; 
    for(auto i:a[s]) 
    { 
     if(!visited[i]) 
     { 
      nchild++;//INcrement children of the current vertex 
      parent[i]=s; 
      DFS(i); 
      low[s]=min(low[s],low[i]); 
      /* s is an articulation point iff 
      1. It the the root and has more than 1 child. 
      2. It is not the root and no vertex in the subtree rooted at one of its 
       children has a back-link to its ancestor. 
       A child has a back-link to an ancestor of its parent when its low 
       value is less than the discovery time of its parent.*/ 
       if((parent[s]==-1 && nchild>1)||(parent[s]!=-1 && low[i]>=disc[s])) 
        ap.pb(s);//Adding the articulation points. How are they repeated? 
     } 
     else if(visited[i] && i!=parent[s]) 
      low[s]=min(low[s],disc[i]); 
    } 

} 

void ArticulationPoints(int n)//Driver Funtion 
{ 
    ap.clear(); 
    rtime=0;//The time for each cycle of DFS 
    for(int i=0;i<n;i++) 
    { 
     parent[i]=-1;//Initializing parents as -1. True for roots 
     visited[i]=0;//All points not visited 
     low[i]=disc[i]=INT_MAX; 
    } 
    for(int i=0;i<n;i++) 
     if(!visited[i])//Vertex not discoverdd 
      DFS(i); 
} 

int main() 
{ 
    int n,m;//number of vertices, edges 
    cin>>n>>m; 
    for(int i=0;i<m;i++)//Building Graph 
    { 
     int x,y; 
     cin>>x>>y; 
     a[x].pb(y); 
     a[y].pb(x); 
    } 
    ArticulationPoints(n);//Calculating Articulation points 
    cout<<"Articulation Points are:\n"; 
    for(int i:ap) 
     cout<<i<<endl; 
    return 0; 
} 

代碼輸入和輸出：http://ideone.com/u5dYOy（見2是怎麼來三次？）

爲什麼會發生這種情況？我在算法中遺漏了什麼？我相信我對算法的運行有一個公平的想法。任何幫助表示讚賞。由於

Answer 1

#include <bits/stdc++.h> 

Don't do this.

除此之外，在許多方面的僞代碼流浪狗。作爲參考，這裏是你鏈接到僞代碼：

GetArticulationPoints(i, d) 
    visited[i] = true 
    depth[i] = d 
    low[i] = d 
    childCount = 0 
    isArticulation = false 
    for each ni in adj[i] 
     if not visited[ni] 
      parent[ni] = i 
      GetArticulationPoints(ni, d + 1) 
      childCount = childCount + 1 
      if low[ni] >= depth[i] 
       isArticulation = true 
      low[i] = Min(low[i], low[ni]) 
     else if ni <> parent[i] 
      low[i] = Min(low[i], depth[ni]) 
    if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1) 
     Output i as articulation point 

1. 你沒有d參數。相反，你增加一個全局變量。但是你永遠不會減少這個變量，所以當你訪問更多的節點時它會不斷增長。在僞代碼中，d表示您在樹中的當前深度。兩個兄弟姐妹應該有相同的深度，但在你的情況下，一個將有更大的深度。

   據我所知，這個算法沒有什麼區別，但是如果你不遵循僞代碼，它總的來說可能是bug的來源。無論如何應該避免全局變量。

   解決方案：的int d參數添加到您的功能和處理它像僞代碼顯示您：通過添加+ 1到它時，你遞歸調用的函數。初始值可以是任何值，但通常設置爲0或1。

2. 您的if條件和比它們在僞代碼中更復雜。我不知道他們是否一定是錯誤的，但是這個，加上你使用的不同名字，可能會引入錯誤。如果第一次實施，並且你依賴僞碼很多，我建議你堅持自己的風格。

   解決方案：改變DFS功能：

   void DFS(int s, int d) 
   { 
       visited[s]=1; 
       low[s]=disc[s]=d; 
       int nchild=0; 
       int isArticulation = 0; 
       for(auto i:a[s]) 
       { 
        if(!visited[i]) 
        { 
         nchild++;//INcrement children of the current vertex 
         parent[i]=s; 
         DFS(i, d + 1); 
         low[s]=min(low[s],low[i]); 
         /* s is an articulation point iff 
         1. It the the root and has more than 1 child. 
         2. It is not the root and no vertex in the subtree rooted at one of its 
          children has a back-link to its ancestor. 
          A child has a back-link to an ancestor of its parent when its low 
          value is less than the discovery time of its parent.*/ 
          if (low[i] >= disc[s]) 
           isArticulation = 1; 
        } 
        else if(i != parent[s]) 
         low[s] = min(low[s], disc[i]); 
       } 
   
       if ((parent[s] != -1 && isArticulation) || (parent[s] == -1 && nchild > 1)) 
        ap.pb(s); 
   } 
   

   你到了最後if你if not visited條件，我猜是什麼導致你的重複（因爲可能有多個內i這樣那low[i] >= disc[s]，所以你正在存儲它們所有的關節點），雖然我沒有檢查它。

我還建議你使用更好的變量名稱，以便知道代表什麼。它會使算法的實際邏輯更容易理解。