Statement: Standard Tarjan is used when judging useful cross-sections and ancestral edges.\(low_x = \min(low_x,dfn_v)\), but after my verbal debate with Doubao and deepseek, the horizontal fork and ancestral side that proves useful is used when using\(low_x = \min(low_x,low_v)\)There is no problem, and it is more intuitive and easy to understand.
1. Problem introduction
When you ask for cut points/edge edges/point dual-connection components/edge double-connection components/strong connected components, they can all be solved by one algorithm, and the codes are not much different, and this algorithm is Tarjan.
2. What is strong connectivity component
For a directed graph\(S\)Sub-picture\(V\),satisfy\(V\)The points inside can be reached between two and two, and there is no sub-picture\(G\)Make\(G \supseteq V,G \not= V\)In layman's terms, it is a pair of accessible sub-pictures that cannot continue to expand.
3. Tarjan seeks the derivation of the powerful connected component algorithm
First of all, for a directed graph search tree, it is divided into 4 types of edges: tree edge, home rebirth edge, horizontal fork edge, and forward edge. The edge of a tree is to search for normal edges in the tree. The edge of an ancestor is a point that returns to one edge of its ancestor. The edge of a horizontal fork is a point that connects to a point that is not its ancestor or its descendant. The edge of a forward is a point that connects to its descendant (not its son).
Then there is the process of the algorithm, which has two arrays\(dfn\)and\(low\), respectively represent the current point\(\operatorname{dfs}\)The minimum that can be reached by the sequence and current point\(dfn\), it's a bit like checking the collection, the one in Tarjan\(low\)The array is similar and searches the\(f\)Arrays, first according to the characteristics of the search tree, their points set on the search tree are\(dfn\)It is continuous, and you will find that any strong connection component has a commanding height\(x\)(Similar to the root of the connected block of the graph and search for the graph), so\(low_x = x\), which is equivalent to finding and searching for the root of a connected block, so we have a bold guess, first prepare a stack and store all points, we first find out when searching\(low\)Array and\(dfn\)Array, if found during search\(low_x = x\), indicating that a commanding height of a strong connected component has been found, and the number of strong connected components has been added to the\(1\), and delete this strong connected component from the stack.
However, we will face a problem: how to ask\(low\)（\(dfn\)Is it easy to ask for)?
You may immediately think of using:
low[x] = min(low[x],low[v]);
Come and ask for it\(low\), but you will find that this may not necessarily result in the correct\(low\), because your father may have updated it, but your son cannot update it in time, but...
It's really necessary to ask for the right one\(low\)Is it?
Actually, it's not necessary.
Because ours\(low\)Its function is actually just to find out the commanding heights of the strong connectivity component, that is, to judge\(low_x\)Is it equal to\(dfn_x\), so even if we\(low\)The inability to update the correct answer in real time does not affect our finding the commanding heights of each strong connection component.
Then let me talk about it again. When you encounter an attributive edge or a horizontal fork edge or forward edge that has not been included in any strong connected component during search, you do not need to search. You can use the above statement to update directly.\(low\), if it is an ordinary tree edge, search first and then update\(low\), there is nothing to do in other situations.
4. Tarjan seeks to connect the weight board
The code is very simple, with only a few lines of important parts.
#include<bits/stdc++.h>
using namespace std;
const int N = ;//Here is the array size, determined according to the data range of the question
vector<int>a[N];//Edge Set
vector<int>g[N];//Save each strong connected component
int cnt,scc_cnt,top;//Denote the current dfs order, and several strong connected components are found at the top of the stack
int dfn[N],low[N];//Same as dfn and low mentioned above
int scc_color[N];//Indicate how many strongly connected components each point belongs to
int sta[N];//Stack
void dfs(int x)
{
dfn[x] = low[x] = ++cnt;//First find dfn, and then assign a initial value to each low
sta[++top] = x;//Put into the stack
for(int v:a[x])
{
//The method of updating low mentioned above
if(!dfn[v])
{
dfs(v);
low[x] = min(low[x],low[v]);
}
else if(!scc_color[v])
{
low[x] = min(low[x],low[v]);
}
}
if(dfn[x] == low[x])//Find the commanding heights
{
scc_cnt++;//The number of strongly connected components +1
int u;
do
{
u = sta[top--];//Take out the top of the stack
scc_color[u] = scc_cnt;// Mark the strongly connected component number
g[scc_cnt].push_back(u);//Put this point in the strong connectivity component to which this point belongs
}
While(u!=x);//Because their point set is continuous in the search tree for any strongly connected component, it cannot be deleted from the commanding height point of this strongly connected component (the top of the stack must be the commanding low point of this strongly connected component, this principle is very simple).
}
}
int vis[N];
signed main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
a[x].push_back(y);//Connect the edge
}
for(int i = 1;i<=n;i++)
{
if(!dfn[i])//Because the graph does not necessarily connect, you have to search all the connected blocks once
{
dfs(i);
}
}
//Decide what to output according to the question requirements
return 0;
}Note: This is just a board, please adapt to the situation when applying.
5. Tarjan: Shrinking Points for Strengthening Connecting Components
There are some questions that require shrinking each strong connection component into one point in order to be better processed, the code volume will be better written, and it will become more intuitive and easy to understand.
So we first use Tarjan to find the strongly connected component, and then retain the two ends of all edges that are not on the same strongly connected component.
Code:
vector<int>e[N];
int x[N],y[N];
for(int i = 1;i<=m;i++)
{
if(scc_color[x[i]]!=scc_color[y[i]])
{
e[scc_color[x[i]]].push_back(scc_color[y[i]]);
}
}
\(x,y\)The array represents the two ends of each edge.\(e\)The array represents the edge set after the shrinking point.
After shrinking the point, there are only one point of the strongly connected component.
6. Tarjan's example of how to find strength and connectivity
B3609 [Graph Theory and Algebraic Structure 701] Strong Connected Components
This question is a board question that can strengthen the connection and connect the weight, just put the board directly.
Since the question requirements are very special, we need to prepare one\(vis\)Array, indicating whether the current point has been outputted at the time of output.
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
vector<int>a[N];
vector<int>g[N];
int cnt,scc_cnt,top;
int dfn[N],low[N];
int scc_color[N];
int sta[N];
void dfs(int x)
{
dfn[x] = low[x] = ++cnt;
sta[++top] = x;
for(int v:a[x])
{
if(!dfn[v])
{
dfs(v);
low[x] = min(low[x],low[v]);
}
else if(!scc_color[v])
{
low[x] = min(low[x],low[v]);
}
}
if(dfn[x] == low[x])
{
scc_cnt++;
int u;
do
{
u = sta[top--];
scc_color[u] = scc_cnt;
g[scc_cnt].push_back(u);
}
while(u!=x);
sort(g[scc_cnt].begin(),g[scc_cnt].end());//Sort according to the point number required by the question
}
}
int vis[N];
signed main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
a[x].push_back(y);
}
for(int i = 1;i<=n;i++)
{
if(!dfn[i])
{
dfs(i);
}
}
printf("%d\n",scc_cnt);
for(int i = 1;i<=n;i++)
{
//Output according to the question requirements
if(vis[i])
{
continue;
}
for(int x:g[scc_color[i]])
{
vis[x] = 1;
printf("%d ",x);
}
printf("\n");
}
return 0;
}P3387 【Template】Shrink points
Since we can repeat the passing points, but the weight is only calculated once, and it is a directed graph, we can first shrink the point, and then it becomes a directed graph that cannot repeat the passing points. Find the path edge weight and maximum value. It is easy to find that we can use topological sort to find the answer.
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
vector<int>a[N];
int cnt,scc_cnt,top;
int dfn[N],low[N];
int scc_color[N];
int sta[N];
vector<int>e[N];
int x[N],y[N];
int dep[N];
int q[N];
int val[N];
int f[N];
int s[N];
void dfs(int x)
{
dfn[x] = low[x] = ++cnt;
sta[++top] = x;
for(int v:a[x])
{
if(!dfn[v])
{
dfs(v);
low[x] = min(low[x],low[v]);
}
else if(!scc_color[v])
{
low[x] = min(low[x],low[v]);
}
}
if(dfn[x] == low[x])
{
scc_cnt++;
int u;
do
{
u = sta[top--];
scc_color[u] = scc_cnt;
}
while(u!=x);
}
}
signed main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
{
scanf("%d",&val[i]);
}
for(int i = 1;i<=m;i++)
{
scanf("%d %d",&x[i],&y[i]);
a[x[i]].push_back(y[i]);
}
for(int i = 1;i<=n;i++)
{
if(!dfn[i])
{
dfs(i);
}
}
for(int i = 1;i<=n;i++)
{
s[scc_color[i]]+=val[i];
}
for(int i = 1;i<=scc_cnt;i++)
{
f[i] = s[i];
}
for(int i = 1;i<=m;i++)
{
if(scc_color[x[i]]!=scc_color[y[i]])
{
e[scc_color[x[i]]].push_back(scc_color[y[i]]);
dep[scc_color[y[i]]]++;
}
}
int h = 1,t = 0;
for(int i = 1;i<=scc_cnt;i++)
{
if(!dep[i])
{
q[++t] = i;
}
}
while(h<=t)
{
int x = q[h++];
for(int v:e[x])
{
f[v] = max(f[v],f[x]+s[v]);
dep[v]--;
if(!dep[v])
{
q[++t] = v;
}
}
}
int maxx = 0;
for(int i = 1;i<=scc_cnt;i++)
{
maxx = max(maxx,f[i]);
}
printf("%d",maxx);
return 0;
}
Tarjan will also be updated later to find the cutting edge/cut point/point double connected components/edge double connected components, so stay tuned! !