Articulation points in a Graph?

Правка en2, от pvpcoder, 2015-08-20 21:17:52

I am Learning Articulation points in Graph thoery which is an application of DFS.I wrote the code by taking reference from GeeksforGeeks [Atriculation Points].(http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/)


void dfs(int u) { static int time=0; int child=0; vis[u]=1; dis_t[u]=low[u]=++time; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!vis[v]) { child++; parent[v]=u; dfs(v); low[u]=min(low[u],low[v]); if(parent[u]==-1 and child>1) { AP[u]=1; } if(parent[u]!=-1 and low[v]>=dis_t[u]) AP[u]=1; } else if(v!=parent[u]) low[u]=min(low[u],dis_t[v]); } }

I came across two conditions.
a vertex u is articulation point if one of the following two conditions is true.
1) u is root of DFS tree and it has at least two children.
2) u is not root of DFS tree and it has a child v such that no vertex in subtree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.

First condition is clear,but I can,t understand the second one.Hoping some help:)

Теги #dfs, articulation point

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский pvpcoder 2015-08-20 21:17:52 30
en1 Английский pvpcoder 2015-08-20 21:16:33 1115 Initial revision (published)