Блог пользователя pvpcoder

Автор pvpcoder, история, 11 лет назад, По-английски

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:)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

well, suppose that for every child v_i of u there is a back edge to some ancestor of u in the dfs-tree. This means that there is a cycle in our graph containing u, therefore u cannot be an articulation point. If however for some child v there is no back-edge which leads to an ancestor of u, then by cutting out u from the graph, we are disconnecting the component containing v.