Finding Articulation Points

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
EduardoQuintana
Posts: 14
Joined: 7 years ago
Gender:

Finding Articulation Points

Does anyone knows why the following algorithm is used for finding articulation points?:

Code: Select all

``````void dfs(int v, int p){
disc[v]=back[v]=++depth;
if(!disc[*i]){
dfs(*i,v);
back[v]=min(back[v],back[*i]);
if((disc[v]!=1 && disc[v]<=back[*i])||(disc[v]==1 && disc[*i]>2))
art[v]=1;// (v) is an articulation point
}else back[v]=min(back[v],disc[*i]);
}
}
``````

Code: Select all

``````void dfs(int v, int p){
disc[v]=back[v]=++depth;
if(!disc[*i]){
dfs(*i,v);
if((disc[v]!=1 && disc[v]<=back[*i])||(disc[v]==1 && disc[*i]>2))
art[v]=1;// (v) is an articulation point
}
back[v]=min(back[v],back[*i]);
}
}
``````
Notice I updated back[v]=min(back[v],back[*i]); instead of back[v]=min(back[v],disc[*i]); for already visited nodes *i.
I do not know if this is algorithm is right nor wrong, I do not have a prove of either case.

I tried solving problem 2639 - Ant Hills, and both algorithms got Accepted. However every single Accepted solution other than mine uses the first code.

The question is: Is the second algorithm right or wrong? Can you prove it?
If it is wrong, then the datasets need refinement.

L@grang3

HaZard
Posts: 115
Joined: 5 years ago
Location: Camagüey - Cuba
Gender:
Contact:

Re: Finding Articulation Points

aqué les dejo mi implementación para buscar los puntos de articulación, ahh ... detecto de otra manera si el nodo de inicio es un punto también (extra > 1):

Code: Select all

``````void dfs(int root) {
num[root] = low[root] = ++gtime;
for(int i = 0; i < ady[root].size(); i++) {