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.
User avatar
EduardoQuintana
Posts: 14
Joined: Fri Nov 18, 2011 9:05 am
Location: Universidad de Cienfuegos (UCf)
Gender: None specified

Finding Articulation Points

Postby EduardoQuintana » Mon May 11, 2015 7:13 pm

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: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: Finding Articulation Points

Postby HaZard » Wed May 13, 2015 7:40 pm

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


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest