I recently learnt the Linear Time Algorithm to calculate the Articulation Points in a graph. My implementation runs correctly on an Online Judge Test Data so there's no issue with the code. However, I seem to have somw difficulty how the same articulation point occurs more than one in the DFS run. Let me explain
I have a list which stores the articulation points if they are encountered. Now when I print the list in the end, I get the correct articulation points but a few vertices which are articulation points occur more than once is the list. According to me this shouldn't be happening since we encounter every vertex only ONCE. So then why am i getting repeated entries in the list? To resolve this, I used a HashSet in my original code to store them and just printed the contents in the end which gave the the correct answer. Here is my code with the issue. The algorithm is primarily based off the pseudocode on wikipedia here: https://en.wikipedia.org/wiki/Biconnected_component
Here is my code for the implmentation in 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 with input and output: http://ideone.com/u5dYOy (See how the 2 comes thrice?)
Why does this happen? Am I missing something in the algorithm. I believe I have a fair idea of the running of the algorithm. Any help is appreciated. Thanks
#include <bits/stdc++.h>
Other than that, your code strays from the pseudocode in a number of ways. For reference, here is the pseudocode you linked to:
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
You have no d parameter. Instead, you increment a global variable. But you never decrement this variable, so it will keep growing as you visit more nodes. In the pseudocode, d represents the current depth you are at in the tree. Two siblings should have the same depth, but in your case, one will have bigger depth.
As far as I can see, this makes no difference for this algorithm, but still, it can be a source of bugs in general if you don't follow the pseudocode. And global variables should be avoided anyway.
Solution: add an int d parameter to your function and handle it like the pseudocode shows you: by adding + 1 to it whenever you call the function recursively. The initial value can be anything, but it's usually set to 0 or 1.
Your if conditions and more complex than they are in the pseudocode. I don't know if they're necessarily wrong, but this, coupled with the different names you're using, can introduce bugs. If implementing for the first time and you're relying on the pseudocode a lot, I suggest you stick to its style.
Solution: change the DFS function to:
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);
}
You had the last if inside your if not visited condition, which I'm guessing is what was causing your duplicates (because there might be multiple i such that low[i] >= disc[s], so you were storing the articulation point for all of them), although I didn't check it.
I also suggest you use better variable names so you know what represents what. It will make the actual logic of the algorithm easier to understand as well.