This article contains the tarjan Finding Strongly Connected Components, Edge Biconnected Components, and Cutting Points sections.
tarjan Seek point bi-connected components, bridges (cut edges) in the next post.
The great Robert Tarjan created a number of well known algorithms and data structures, the most famous of which are (in this paper) the connectivity-related tarjan algorithm, Splay-Tree, Toptree, tarjan for lca, and so on.
Note: Strongly connected components of directed graphs, bi-connected components of undirected graphs, and tarjan for nearest common ancestor are known as the three major algorithms of tarjan.
So at the beginning of this blog, %%% Tarjan Dalao.
Foundational Concepts:
strongly connected component：
For adirected graph G, there exists a subgraph such that any point in the subgraph can be reached from every point in the subgraph, then this subgraph is said to be a strongly connected component of G. In particular, a point is also a strongly connected component.
The red boxed portions of the following figure are all strongly connected components: (obviously, points 1, 2, 3, and 5 in the red box can reach each other)
cutoff point：
For aundirected connectivity map (math.) G. If G becomes no longer connected after removing a node u in G and deleting all edges connected to that node, the point u is said to be a cut point.
The red point 4 in the icon below is the cut point:
Cutting Edge (Bridge):
In a connected component, if the deletion of a certain edge will split this connected component into two connected components, then this edge is called a cut edge (bridge).
The red edge of this diagram
Point/edge bi-connected components:
If aundirected graphA graph in which the removal of any node (an edge) does not change the connectivity of this graph, i.e., there is no cut point (bridge), is called a point (edge) bi-connected graph. They are referred to as point-dual and edge-dual, respectively.
This graph is both a point double and a side double (obviously it contains neither cut points nor bridges):
Prior knowledge:
It is recommended to understand on your own first
dfs spanning tree
Image taken fromoi-wiki
neighboring linked list
The depository side of the way to learn on their own (
tarjan for strongly connected components (must see):
Two arrays need to be maintained:
\(dfn_i\):: Indicates\(i\) The dfs sequence at this point (i.e., the point at which depth-first search traverses the\(i\) (order searched)
\(low_i\): Indicates that from a point-based\(i\) is the minimum number of nodes in the subtree of the root node that can be reached at any point through a single returning edge
Algorithmic Thoughts:
Maintain a stack that holds the nodes of the strongly connected component being looked for.
Perform a depth-first search on each node of the graph while maintaining each point's\(low、dfn\) value, adding it to the stack each time a point is searched. Whenever a strongly connected element is found (if a point's\(low\) sum\(dfn\) values are equal, we call this point a strongly connected element), a strongly connected component is actually found in its entirety.
Thought Analysis (Difficult Questions):
- How to update\(low\) Value?
For points found during the search\(u\) point in the direction of\(v\), there are the following three scenarios:
1 . Point .\(v\) has not yet been accessed: at this point we continue with the\(v\) Perform a search. In the backtracking process use\(low_v\) update\(low_u\). Because.\(v\) The points in the subtree of\(u\) the midpoint of the subtree, then\(v\) A point in the subtree can reach\(x\) point, which is the\(u\) The point in the subtree reaches the\(x\) Point.
2 . Dot\(v\) Visited and already on the stack: (i.e., in the current strongly connected component), being visited indicates that\(v\) In the search tree is\(u\) of the ancestor node, then from the\(u\) walk\(v\) The side that we are updating is the side that we are updating.\(low\) The one to be used is the reentrant edge, so it's a good idea to use\(dfn_v\) value update\(low_u\)；
3 . Dot\(v\) Visited but not in the stack: indicates that the strongly connected component where the point is located has already been found and the point is not in the strongly connected component that is now being looked for, then no operation is needed.
- Why does finding a strongly connected element currently find all of a strongly connected component?
We know that strong connectivity elements\(x\) there are\(low_x = dfn_x\)The description is based on\(x\) All points in the subtree rooted at are unreachable\(x\) points (in the same strongly connected component) before then\(x\) It is the "starting point" of this strong connectivity component.
Based on the stack's first-in-last-out property, it can be known that the stack from the\(x\) The points to the top of the stack are\(x\) points within the subtree and is the same as\(x\) that belong to the same strongly connected component. Then find the\(x\) After this strongly concatenated element, the stack from the\(x\) Go to the top of the stack and take out all the points (these are the points in the current strongly connected component).
Pseudocode:
tarjan(point x){
low[x] = dfn[x] = ++th; // update the dfs sequence
Put x on the stack;
for(enumerate points y adjacent to x){
if(y has not been searched){
tarjan(y); }
low[x] = min(low[x], low[y]); }
}
if(y is searched and already on the stack){
low[x] = min(low[x], dfn[y]);
}
}
if(x is a strongly connected element){
scc++; //scc is the number of strongly connected components
Remove elements from the stack in order from x to the top of the stack; }
}
}
Algorithm Demo:
black borderedge of a treeThe blue edge isrejoining border；
In this connectivity graph, we dfs with point 1 as the root, and all points are labeled with their dfs order:
We start dfs from 1, add 1 to the stack, find the point 2 adjacent to 1, and find that 2 has not been searched yet, then recursively dfs 2;
Add 2 to the stack, find point 3 adjacent to 2. 3 is also unsearched, and recursively search for 3;
Also add 3 to the stack, and find that the point 1 adjacent to 3 has already been searched and is already on the stack, then the edge from 3 to 1 is an ancestor edge, use\(dfn_1\) update\(low_3\), backtracking;
The backtracking process is done separately with\(low_3\) update\(low_2\)， \(low_2\) update\(low_1\)。
Backtracking to node 1 with\(low_1 = dfn_1\)If node 1 is a strongly connected element, then all elements in the stack from 1 to the top of the stack are a strongly connected component.
Algorithm code:
int th, top, scc; //S denotes the timestamp, top of the stack, and number of strongly connected components of the dfs, respectively.
int s[N], ins[N]; //s is the handwritten stack, ins[i] indicates whether the point i is on the stack or not
int low[N], dfn[N], belong[N]; //belong[i] denotes the label of the strongly connected component to which i belongs.
void tarjan(int x){
low[x] = dfn[x] = ++th;
s[++top] = x, ins[x] = true;
for(int i=head[x]; i; i=nxt[i]){ //chain forward star storage edges
int y = to[i].
if(!dfn[y]){ //if y hasn't been searched yet
tarjan(y); // search for y
low[x] = min(low[x], low[y]);
}
else if(ins[y]){ // y is on the stack
low[x] = min(low[x], dfn[y]); }
}
}
if(low[x] == dfn[x]){
++scc;
do{ //remove all elements from x to the top of the stack
belong[s[top]] = scc;
ins[s[top]] = false;
}while(s[top--] ! = y); }
}
}
However, most questions are not given a connected graph, so a graph may be split into multiple strongly connected components, so the main function should be written this way (to ensure that each strongly connected component is run through the tarjan):
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i);
Example question:
Do not rush to read the following content, it is recommended to do one or two sample problems to familiarize yourself with the algorithmic principles and code before continuing to study.
The Cow Prom S[USACO06JAN](Absolute boards)
Board!
Messaging [NOIP2015 Improvement Group]
The special minimal ring problem, because this problem guarantees that each point has out-degree 1, this problem can be done by using tarjan to find the strongly connected component, you can go to the other problems to see the solution (Like this one.）。
Popular Cattle [USACO03FALL / HAOI2006]
The idea of shrinking points, but it is well understood, to find out the strong connectivity component, each strong connectivity component is regarded as a big point, calculate the out degree of each big point, if there is a big point with out degree 0, all the cows contained in this big point are star cows; if there are two or more big points with out degree 0 (then all the adoration in these big points can not be propagated), then G, and there will be no star cows.
Look at the code for the exact implementation
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, out[N];
int low[N], dfn[N], ins[N], th;
int s[N], belong[N], top, scc, size[N];
int head[N], to[N], nxt[N], tot;
void addedge(int x, int y){
to[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void tarjan(int x){
low[x] = dfn[x] = ++th;
s[++top] = x, ins[x] = true;
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(!dfn[y]){
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if(ins[y]){
low[x] = min(low[x], dfn[y]);
}
}
if(low[x] == dfn[x]){
++scc;
do{
size[scc]++;
belong[s[top]] = scc;
ins[s[top]] = false;
}while(s[top--] != x);
}
}
int main(){
ios::sync_with_stdio(false), (0), (0);
cin>>n>>m;
for(int i=1; i<=m; i++){
int x, y; cin>>x>>y;
addedge(x, y);
}
for(int i=1; i<=n; i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1; i<=n; i++){
for(int j=head[i]; j; j=nxt[j]){
int y = to[j];
if(belong[i] != belong[y]) out[belong[i]]++;
}
}
int cnt = 0, ans = 0;
for(int i=1; i<=scc; i++){
if(out[i]) continue;
cnt++;
if(cnt > 1){cout<<0; return 0;}
ans = size[i];
}
cout<<ans;
return 0;
}
tarjan Finding edge bi-connected components
One implementation is to run the cut bridge before finding the side double, this method is not described in this article.
In fact, we can find that the edge double connected component is a strong connected component to get into the undirected graph, the idea of finding the edge double is also the same as the strong connected component. (Look at the code to understand can be, very simple)
The differences with strongly connected components are labeled in the code.
Algorithm code:
void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x, ins[x] = true;
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(y == p) continue;// because of the bidirectional edges so add a judgment node to the search
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
}
else low[x] = min(low[x], dfn[y]);
// since in an undirected graph, if y has already been searched then it must be an ancestor of x, no need to judge ins again
}
if(dfn[x] == low[x]){
++scc;
do{
belong[s[top]] = scc;
SCC[scc].emplace_back(s[top]); //store the side double, optionally write this as needed for the topic
}while(s[top--] ! = x);
}
}
But pay attention to the requirements of the topic, sometimes the topic may have heavy edges, the search process can not only special judgment of the father node, but should remember the number of the edge judgment edge. Because there are heavy edges, then you can go back to the father node.
Example question:
[Template] Side Double Link Component
Board questions, but note that the questions may have overlapping edges, so you need to keep track of the edges to prevent "backtracking".
Just look at the code.
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int n, m, top, th, cnt;
int s[N], low[N], dfn[N], id[N];
int tot, head[N], to[N], nxt[N];
vector<vector<int> >ans;
inline void addedge(int x, int y){
to[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
id[tot] = cnt; //id Let's remember the side numbers.
}
inline void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x;
for(int i=head[x]; i; i=nxt[i]){
int y(to[i]), edge = id[i];
if(edge == p) continue; //Solving Heavy Edge Problems
if(!dfn[y]){
tarjan(y, edge);
low[x] = min(low[x], low[y]);
}
else low[x] = min(low[x], dfn[y]);
}
if(low[x] == dfn[x]){
vector<int>scc;
do scc.emplace_back(s[top]);
while(s[top--] != x);
ans.emplace_back(scc);
}
}
int main(){
ios::sync_with_stdio(false), (0), (0);
cin>>n>>m;
for(int i=1; i<=m; i++){
int x, y; cin>>x>>y;
if(x == y) continue; ++cnt;
addedge(x, y), addedge(y, x);
}
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i, 0);
cout<<()<<"\n";
for(auto x : ans){
cout<<()<<" ";
for(auto i : x){
cout<<i<<" ";
}
cout<<"\n";
}
return 0;
}