Points d'articulation apparaissant à plusieurs reprises dans l'implémentation de Tarjan

Question

J'ai récemment appris l'algorithme de temps linéaire pour calculer les points d'articulation dans un graphique. Ma mise en œuvre s'exécute correctement sur un test en ligne Judge Test Data afin qu'il n'y ait pas de problème avec le code. Cependant, il semble que j'ai de la difficulté à comprendre comment le même point d'articulation survient plus d'un dans la série DFS. Laissez-moi vous expliquer

J'ai une liste qui stocke les points d'articulation si elles sont rencontrées. Maintenant, quand j'imprime la liste à la fin, j'obtiens les bons points d'articulation mais quelques sommets qui sont des points d'articulation se produisent plus d'une fois dans la liste. Selon moi, cela ne devrait pas se produire puisque nous ne rencontrons chaque sommet qu'une seule fois. Alors, pourquoi suis-je obtenir des entrées répétées dans la liste? Pour résoudre ceci, j'ai utilisé un HashSet dans mon code original pour les stocker et j'ai juste imprimé le contenu à la fin qui a donné la bonne réponse. Voici mon code avec le problème. L'algorithme est principalement basé sur l'pseudocode sur wikipedia ici: https://en.wikipedia.org/wiki/Biconnected_component

Voici mon code pour le implmentation en C++:

/*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; 
} 

Code avec entrée et sortie: http://ideone.com/u5dYOy (voir comment les deux vient trois fois?)

Pourquoi cela se produit-il? Ai-je manqué quelque chose dans l'algorithme? Je crois avoir une idée juste du fonctionnement de l'algorithme. Toute aide est appréciée. Merci

Answer 1

#include <bits/stdc++.h> 

Don't do this.

Autre que cela, vos chiens errants de code du pseudo-code dans un certain nombre de façons. Pour référence, voici le pseudo-code vous avez accédé à:

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. Vous avez aucun paramètre d. Au lieu de cela, vous incrémentez une variable globale. Mais vous ne décrémentez jamais cette variable, donc elle continuera de croître lorsque vous visiterez plus de nœuds. Dans le pseudocode, d représente la profondeur actuelle dans laquelle vous vous trouvez dans l'arborescence. Deux frères et sœurs devraient avoir la même profondeur, mais dans votre cas, on aura une plus grande profondeur. Pour autant que je puisse voir, cela ne fait aucune différence pour cet algorithme, mais il peut quand même être une source de bugs en général si vous ne suivez pas le pseudo-code. Et les variables globales devraient être évitées de toute façon.

   Solution: ajouter un paramètre int d à votre fonction et le manipuler comme le montre pseudocode: en ajoutant + 1 à chaque fois que vous appelez la fonction récursive. La valeur initiale peut être n'importe quoi, mais elle est généralement définie sur 0 ou 1.

2. Vos conditions if et plus complexes qu'elles ne le sont dans le pseudocode. Je ne sais pas s'ils ont nécessairement tort, mais cela, couplé avec les différents noms que vous utilisez, peut introduire des bugs. Si vous mettez en œuvre pour la première fois et que vous comptez beaucoup sur le pseudo-code, je vous suggère de rester fidèle à son style.

   Solution: changer la fonction 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); 
   } 
   

   avait la dernière if dans votre état if not visited, que je devine est ce qui a été la cause de vos doublons (car il pourrait y avoir plusieurs i tels que low[i] >= disc[s], donc vous étiez en train de stocker le point d'articulation pour chacun d'entre eux), même si je ne l'ai pas vérifié.

Je vous suggère également d'utiliser de meilleurs noms de variables afin de savoir ce que représente quoi. Cela rendra également la logique de l'algorithme plus facile à comprendre.