Finding Articulation Points

[EduardoQuintana]

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;
	for(viit i=adj[v].begin(); i!=adj[v].end(); i++)if(*i != p){
		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]);
	}
}

instead of

Code: Select all

void dfs(int v, int p){
	disc[v]=back[v]=++depth;
	for(viit i=adj[v].begin(); i!=adj[v].end(); i++)if(*i != p){
		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.

[HaZard]

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++) {
        int to = ady[root][i];
        if(!low[to]) {
            p[to] = root;
            dfs(to);
            if(root == 1)extra++;
            if(num[root] <= low[to])
                ap[root] = true;
            low[root] = min(low[root], low[to]);
        }
        else if(to != p[root])
            low[root] = min(low[root], num[to]);
    }
}