For Tribal Members Only

## Introduction to Tarjan algorithm

The Tarjan algorithm is based on a depth-first search algorithm that defines the order number (timestamp) of the nodes where DFN(u) is the node and the order number of the earliest node that a subtree with Low(u) is the u or u can trace back to

C++ code, using a chain forward star map

#include<bits/stdc++.h> using namespace std; struct node{ int to, nxt; }e[M]; int n, m, hd[N], dfn[N], low[N], cnt, tot; void add(int u, int v){ e[++cnt].to = v; e[cnt].nxt = hd[u]; hd[u] = cnt; } void tarjan(int u){ dfn[u] = low[u] = ++tot; for(int j = hd[u]; j; j = e[j].nxt){ int v = e[j].to; // v is a child node of u if(!dfn[v]){ tarjan(v); if(low[u] > low[v]) low[u] = low[v]; }else{ //It's important to note here that some of the code is written as downline comments //This method of writing will make mistakes when calculating cut points. Is there any analysis below the article??? // if(low[u] > low[v]) low[u] = low[v]; if(low[u] > dfn[v]) low[u] = dfn[v]; } } } int main() { cin >> n >> m; int u, v; for(int i = 1; i <= m; i++){ scanf("%d%d", &u, &v); add(u, v); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); return 0; }

## Tarjan cut point

In an undirected connected graph, if one of the points and all the edges connecting the points are removed, the graph is no longer connected, and this point is called a secant point.

How to Use Tarjan to Find Cutting Points

case1: son of dfn[x] <= low[x] not root node

For edges (u, v), if dfn[u]<=low[v], that is, V is the earliest point that its subtree can go back to, and it can only be u at the earliest time. To get to u, the back edge of u or the parent-child edge of u are needed. That is to say, if u is removed, the back edge of u and the parent-child edge of u will disappear, then the earliest point that V can trace back to is behind u and cannot reach the vertex before u, where u is the cut point.

case2:root node number of sons >=2

Explain the graph on the right here, because there is a path connection between A and B, so the order of dfs is root->A->B, so root has only one son, root is not a cut point

Why should root be considered separately? In the following figure, Tarjan runs and all points have a low of 1

low[root] == dfn[root], satisfies case1, but root is obviously not a cut point, so it needs to be considered separately

Detailed Code

#include<bits/stdc++.h> using namespace std; const int N = 20001, M = 100001; int n, m, hd[N], cnt; int dfn[N], low[N], tot, num; bool iscut[N]; struct node{ int to, nxt; }e[M * 2]; // Note that because it is an undirected graph, the number of edges is M*2 void add(int u, int v){ e[++cnt].to = v; e[cnt].nxt = hd[u]; hd[u] = cnt; } void tarjan(int root, int u){ dfn[u] = low[u] = ++tot; int child = 0; for(int j = hd[u]; j; j = e[j].nxt){ int v = e[j].to; if(!dfn[v]){ tarjan(root, v); low[u] = min(low[u], low[v]); if(root == u) child++; //You can't count the number of cut points here, it will repeat, dfn[u] <= low[v1], dfn[u] <= low[v2]..... //The u-point is repeated many times if((root == u && child > 1) || (root != u && dfn[u] <= low[v])) iscut[u] = true; } //This must be dfn[v], not low[v] as illustrated below else low[u] = min(low[u], dfn[v]); } } int main() { cin >> n >> m; int x, y; for(int i = 1; i <= m; i++) scanf("%d %d", &x, &y), add(x, y), add(y, x); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, i); for(int i = 1; i <= n; i++) if(iscut[i]) num++; cout << num << endl; for(int i = 1; i <= n; i++) if(iscut[i]) cout << i << " "; return 0; }

Note explaining why can't low[u] = min(low[u], low[v])

Cutting Point Template Title

Video detailing of the messy Big Brother 233 in station b

## Tarjan's Cutting Edge (Bridge)

In an undirected connected graph, if one of the edges is deleted, the graph is no longer connected, and this edge is called a secant edge.

Cut Edge Note that undirected graph edges can only be parent->child, not child->father, otherwise

Under the action of low[u] = min(low[u], dfn[v]), any DFN [parent] >= low[child]

When we use the chain forward star storage edge, the edge number starts from 2, so the two-way edge numbers of the undirected graph are x and x^1. The function of ^1 is to add 1 to even numbers and subtract 1 from odd numbers.

#include<bits/stdc++.h> using namespace std; const int N = 20001, M = 100001; int n, m, hd[N], cnt; int dfn[N], low[N], tot, num; bool iscut[N]; struct node{ int to, nxt; }e[M * 2]; // Note that because it is an undirected graph, the number of edges is M*2 void add(int u, int v){ e[++cnt].to = v; e[cnt].nxt = hd[u]; hd[u] = cnt; } void tarjan(int u, int eid){ dfn[u] = low[u] = ++tot; for(int j = hd[u]; j; j = e[j].nxt){ int v = e[j].to; if(!dfn[v]){ tarjan(root, v); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = true; } //Guarantee not to point to parent node else if(i != (eid ^ 1))low[u] = min(low[u], dfn[v]); } } int main() { cin >> n >> m; int x, y; cnt = 1; for(int i = 1; i <= m; i++) scanf("%d %d", &x, &y), add(x, y), add(y, x); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, 0); for (int i = 2; i < cnt; i += 2) if (bridge[i]) printf("%d %d\n", e[i ^ 1].to, e[i].to); return 0; }

## Tarjan Strongly Connected Component

Strong connectivity: Directed graph, any two-way communication

Strong Connected Component: A strongly connected subgraph of a directed graph, the concept of which is a directed graph divided into many parts, each part can reach each other inside, but different parts cannot reach each other or can only be reached in one direction.

Specific code

#include<bits/stdc++.h> using namespace std; const int N = 20001, M = 100001; int n, m, hd[N], cnt; int dfn[N], low[N], S[N], beLong[N], top, tot, scNum; bool inStack[N]; struct node{ int to, nxt; }e[M * 2]; // Note that because it is an undirected graph, the number of edges is M*2 void add(int u, int v){ e[++cnt].to = v; e[cnt].nxt = hd[u]; hd[u] = cnt; } //Add a new stack, inStack[], a stack top subscript top //A new tag array beLong[] is added to record which strong connected component each vertex belongs to, and the label of the strong connected component scNum void tarjan(int u){ dfn[u] = low[u] = ++tot; inStack[u] = true; //Mark u point is already on the stack S[++top] = u; for(int j = hd[u]; j; j = e[j].nxt){ int v = e[j].to; if(!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]); } //Points in a well-established strongly connected component cannot update the current point //Avoid one-way edges between two strongly connected components, as shown in the following figure else if(inStack[v])low[u] = min(low[u], dfn[v]); } //When all descendant nodes of u have finished searching if(dfn[u] == low[u]){ //The label of the strong connectivity strongly connected component scNum++; int v; do{ v = S[top--]; inStack[v] = false; beLong[v] = scNum; }while(v != u); } } int main() { cin >> n >> m; int x, y; cnt = 1; for(int i = 1; i <= m; i++) // One-way Edge scanf("%d %d", &x, &y), add(x, y); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= n; i++) cout << beLong[i] << " "; return 0; }

else if(inStack[v])low[u] = min(low[u], dfn[v]), if no limitation of inStack[v], the following will occur,

The dfn and low of all points after dfs are 1, resulting in the strong connectivity component composed of 3,4 points not found

Reference to Lough Valley

Biconnected component

## Tarjan Edge-finding Double (E-BCC)

An undirected connected graph without a cut edge (bridge) is called an edge double connected graph

In undirected graph, if u and v cannot be disconnected by deleting that edge, then u and v edges are double connected

That is, the path from u to v does not have to go by an edge

Solution: Tarjan finds the cutting edge, marks the cutting edge, and dyes it once with dfs (no cutting edge is used)

Trajan Cutting Edge void dfs(int u) { beLong[u] = eNum;//dyeing for(int j = hd[u]; j; j = e[j].nxt){ { int v = e[j].to; if (bridge[j]) // Skip Cutting Edge continue; if(!beLong[v]) dfs(v); } } for(int i = 1; i <= n; i++){ if(!beLong[i]) dfs(i); }

P4214 [CERC2015]Juice Junctions

P2860 [USACO06JAN]Redundant Paths G

## Tarjan Point Double (V-BCC)

In undirected graphs, if the deletion of that point (non-u-point and v-point) does not disconnect u and v, then u and V points are dual connected

That is, the path from u to V does not have to go through a point (except u,v)

Note: A graph with two points and one edge is also a BCC

Secant points in undirected connected graphs must belong to at least two BCCs, and non-secant points must belong to only one BCC

The cut points will belong to at least two BCCs even if they are adjacent. The intersections between BCCs are cut points, so non-cut points belong to only one BCC

Solution:

The node is stacked up to a node. If the low value of the target node is not less than the dfn value of the current node, the node is stacked up to the target node (the target node is stacked out), the stack node and the current node are stored in the BCC. For each BCC, the first point it finds in the DFS tree must be the cutting point or the tree root of the DFS tree.

It is proved that the cut point is the intersection point between BCCs, so the cut point is at the edge of the BCC, and the BCC is connected by the cut point, so the first point that BCC is found in the DFS tree is the cut point. The special case is that for the BCC to which the starting point of DFS belongs, the first point discovered is the tree root of the DFS tree

The above result is equivalent to each BCC being in a subtree of its first discovered point (a cut point or tree root)

This way, whenever a BCC is found (low[v]>=dfn[u]), the subtree is stacked and the subtree and the current node (cut point or root) are added to the BCC.

#include<bits/stdc++.h> using namespace std; const int N = 20001, M = 100001; int n, m, hd[N], cnt; int dfn[N], low[N], S[N], top, tot, bNum; vector <int> bcc [N]; struct node{ int to, nxt; }e[M * 2]; // Note that because it is an undirected graph, the number of edges is M*2 void add(int u, int v){ e[++cnt].to = v; e[cnt].nxt = hd[u]; hd[u] = cnt; } //Added BCC variable array vector <int>bcc[N]; void tarjan(int u) { dfn[u] = low[u] = ++tot; S[++top] = u; for(int j = hd[u]; j; j = e[j].nxt){ int v = e[j].to; if(!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]){ //u is a cut point or root bNum++; int v; do{ v = S[top--]; bcc[bNum].push_back(v); }while(u != v); //The cut point belongs to the dual component of multiple points, so the cut point should be put back S[++top] = v; //When can a cut point come out of the stack, only when traversing to another cut point } } else { low[u] = min(low[u], dfn[v]); } } } int main() { cin >> n >> m; int x, y; cnt = 1; for(int i = 1; i <= m; i++) // One-way Edge scanf("%d %d", &x, &y), add(x, y), add(y, x); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= bNum; i++){ for(int j = 0; j < bcc[i].size(); j++) cout << bcc[i][j] << " "; cout << endl; } return 0; }

A point double-connected graph can be solved without crossing a secant point in dfs

SP2878 KNIGHTS - Knights of the Round Table

P3225 [HNOI2012] Mine Setup

P5058 [ZJOI2004] sniffer

## Tarjan Indentation

That is, all strongly connected components derived by tarjan become points (collections or sharing some information), so directed rings become directed acyclic graphs (DAGs)

#include<bits/stdc++.h> using namespace std; const int N = 20001, M = 100001; int n, m, hd[N], cnt; int a[N], dfn[N], low[N], S[N], beLong[N], top, tot; bool inStack[N], exist[N]; struct node{ int u, to, nxt; }e[M * 2]; // Note that because it is an undirected graph, the number of edges is M*2 void add(int u, int v){ e[++cnt].to = v; e[cnt].u = u; e[cnt].nxt = hd[u]; hd[u] = cnt; } //Add a new stack, inStack[], a stack top subscript top //A new tag array beLong[] is added to record which strong connected component each vertex belongs to, and the label of the strong connected component scNum void tarjan(int u){ dfn[u] = low[u] = ++tot; inStack[u] = true; //Mark u point is already on the stack S[++top] = u; for(int j = hd[u]; j; j = e[j].nxt){ int v = e[j].to; if(!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]); } //Points in a well-established strongly connected component cannot update the current point //Avoid one-way edges between two strongly connected components, as shown in the following figure else if(inStack[v])low[u] = min(low[u], dfn[v]); } //When all descendant nodes of u have finished searching if(dfn[u] == low[u]){ //The label of the strong connectivity strongly connected component int v; exist[u] = true; do{ v = S[top--]; inStack[v] = false; beLong[v] = u; //Merging Weights of Strongly Connected Components a[u] += a[v]; }while(v != u); //Finally a[u] + a[u] a[u] /= 2; } } int main() { cin >> n >> m; int x, y; cnt = 1; for(int i = 1; i <= m; i++) // One-way Edge scanf("%d %d", &x, &y), add(x, y); // Enter a weight for each point for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); //Rebuild Map cnt = 0; for(int j = 1; j <= m; j++){ //There will be a double edge after the indentation point, which generally has no effect //Create a new edge if it belongs to two different indentations if(beLong[e[j].u] != beLong[e[j].to]){ add(beLong[e[j].u], beLong[e[j].to]); } } return 0; }

Indentation Point

P2341 [USACO03FALL / HAOI2006] Popular Bovine G