“This is the 14th day of my participation in the Gwen challenge of The 13th Month. See details: The Last Gwen Challenge of 2021”.

Related introduction

Strongly connected component

In a directed graph, a subgraph is a strongly connected component if any two points are connected.

Introduction of algorithm

There are several TarjanTarjanTarjan algorithms, all named after TarjanTarjanTarjan, the TarjanTarjanTarjan algorithm for finding strongly connected components, He dyes the graph in a depth-first search method to obtain the strongly connected components.

Algorithm thought

In a graph with NNN vertices, the TarjanTarjanTarjan algorithm needs to maintain a vertex stack and several arrays.

  1. Stack Sstack\ Sstack S stands for vertex stack.
  2. DFN [] DFN [\] DFN [] ARRAY, DFN [I] DFN [I] DFN [I] indicates the depth search order of the third vertex.
  3. Low []low[\] Low [] Array, low[I]low[I]low[I] Low [I] indicates the minimum DFNDFNDFN to which vertex III can be traceback.
  4. Visit []visit[\]visit[] Array, visit[I]visit[I]visit[I] indicates whether vertex III is in the stack.
  5. Color []color[\]color[] array, color[I]color[I]color indicates which strongly connected component of vertex III, and the same strongly connected component is dyed the same.

Algorithm process

void Tarjan(int u){
	dfn[u]=low[u]=++cnt;// Initialize DFN =low
	S.push(u);// vertex u is pushed
	visit[u]=1;
	for(inti=head[u]; i; i=last[i]){// iterate over all edges of u
		int v=to[i];//v is the terminating vertex of the edge starting with u
		if(! dfn[v]){// If you haven't accessed v yet
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(visit[i]){
			low[u]=min(low[u],dfn[v]); }}if(dfn[u]==low[u]){
		color[u]=++sum;// Color +1 for the same connected component
		visit[u]=0;// Mark as not accessed
		while(S.top()! =u){ color[S.top()]=color[u];
			visit[S.top= ()]0;// Mark as not accessed
			S.pop(a); }}}Copy the code

extension

In addition to digraphs, strongly connected components can be found, and in undigraphs, cut points and cut edges (Bridges) can also be found.

Cut point: A point in an undirected graph where the removal of a point and its connecting edges breaks the connectivity.

Edge cutting: Removing an edge from an undirected graph that would break connectivity.

The point connected by the cutting edge must be the cutting point, but the edge connected by the cutting point may not be the cutting edge.

Cut point

The TarjanTarjanTarjan algorithm is used to cut points. If there are edges U → VU \to VU →v, if low[V]>= DFN [u]low[V]>= DFN [u]low[v]>= DFN [u] then VVV cannot connect to points earlier than UUu. Uuu is the cut point. In particular, the root node cannot be judged as a cut point based on this relationship. The root node needs to determine whether the subtree is greater than or equal to 222 to be a cut point.

void Tarjan(int u,int fa){
	int child=0;// Number of subtrees
	dfn[u]=low[u]=++cnt;// Initialize DFN =low
	for(inti=head[u]; i; i=last[i]){// iterate over all edges of u
		int v=to[i];//v is the terminating vertex of the edge starting with u
		if(! dfn[v]){// If you haven't accessed v yet
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u! =root) cut[u]=1;// Record the cut point
		}else if(dfn[u]>dfn[v]&&v! =fa){ low[u]=min(low[u],dfn[v]); }}if(u==root&&child>=2) cut[u]=1;
}
Copy the code

Cutting edge

If (low[v]>= DFN [u]&&u! = root) to if (low [v] > DFN [u] && u! =root) can find the number of cut edges.