Cutpoint Tarjan Algorithm

Original link: https://blog.aeilot.top/2022/12/04/cut-vertex/

I recently learned graph theory, and wrote a problem solution to record it.

definition

• For an undirected graph, if the number of maximum connected components of the graph increases after a point is deleted, then this point is the cut point (also known as the cut top) of the graph.

This blog mainly introduces that the Tarjan algorithm is used to find cut points.

cut point

Tarjan algorithm, record the node access time stamp dfn , and the time stamp low of the earliest point that the node can go back to.

For a certain point:

1. If this point is the root node and there are more than two connected components connected to it, then this point is a cut point.
2. If the successor of a certain point is a connected component, and this point is not the root node, then this point is a cut point.

the first case

We need to record the root node fa . When traversing, if fa is repeatedly visited, it means that a connected component under fa has been found.

the second case

Assuming the current point s , for the next node y to visit:

If low[y] >= dfn[s] , it means that there is a connected component under this point.

Note: This is similar to min(low[s],dfn[y]) we did when Tarjan was seeking SCC.

the code

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19

 void tarjan ( int s, int fa) {
 dfn[s] = low[s] = ++cc;
 int child = 0 ;
 for ( int i = head[s]; i!= -1 ; i=NDS[i].next){
 int y = NDS[i].to;
 if (!dfn[y]){
 tarjan (y,fa);
 low[s] = min (low[s], low[y]); // update after backtracking
 if (low[y]>=dfn[s] && s != fa) // Case 2
 cut[s] = 1 ;
 if (s==fa) // case 1 count
 child++;
 }
 low[s] = min (low[s], dfn[y]);
 }
 if (child>= 2 && s==fa){
 cut[s] = 1 ; // case 1
 }
 }

This article is transferred from: https://blog.aeilot.top/2022/12/04/cut-vertex/
This site is only for collection, and the copyright belongs to the original author.