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.
Post Reply
User avatar
EduardoQuintana
Posts: 14
Joined: 6 years ago
Location: Universidad de Cienfuegos (UCf)
Gender: None specified

Finding Articulation Points

Post by EduardoQuintana » 3 years ago

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.


L@grang3

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: Finding Articulation Points

Post by HaZard » 3 years ago

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]);
    }
}
teruel

Post Reply

Return to “Algorithms”