在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]，所以你正在存储它们所有的关节点），虽然我没有检查它。

我还建议你使用更好的变量名称，以便知道代表什么。它会使算法的实际逻辑更容易理解。