Finale: tarjan solves for cut points, point bi-connected components, and cut edges (bridges) (with 40 very good tarjan problems).
Previous (tarjan Finding strongly connected components, shrinking points, and finding edge doubles)
tarjan cut point
neverthelessSeeking Strong Connections FractionThe general idea of the pinch.
Algorithmic Thoughts:
We categorize the points in the graph into two types: each linkage subgraph search starts with theroot node cap (a poem)other points。
The way to determine if it is a cut point is as follows:
-
For the root node：
Keep track of the number of unsearched child nodes from this point in the tarjan run\(child\)If\(child\ge 2\), then the point is a cut point, otherwise it is not a cut point;- Proof (it's very simple, so I suggest you think about why or hand-model a diagram for yourself first, and then read the proof if you really don't understand it):
Let the root node be the point\(u\)If\(child\) is 1, it means that the points in different subtrees of the root node can not pass through point\(u\) and reach each other, which means that even after deleting\(u\) points, all points in the graph are reachable from each other as usual, then\(u\) is not a cut point. Conversely, it is equally easy to prove that it is a cut point.
-
For other points：
Judging a point\(u\) Is there a child node\(v\) feasiblelow[v] >= dfn[u], if it exists, then\(u\) is a cut point, otherwise it is not a cut point.- Proof:
Because when we run a tarjan in an undirected graph, we have already judged the number of the parent node or edge to avoid "backtracking" (see the section on edge doubling above for more details), so if the judgment condition is satisfied, then it means that\(v\) You can only get there by going back to the side of the ancestor.\(u\) and its subtree parts, and does not reach the\(u\) of an ancestor node, so if\(u\) Tap to delete, then\(v\) The point of view is the same as\(u\) The above part is disconnected, at which point it is clear that\(u\) for the cut point.
After you will determine whether these two types of points are cut points are done, I believe you know how to find. Look at the code!
Algorithm code:
Compared to the side double part adds an array ofcut[x] judgement\(x\) is a cut point, if true then\(x\) It's a cut point, otherwise it's not.
void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x; int child = 0;
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(y == p) continue;
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x]){
child++;
if(p != 0 or child > 1) cut[x] = 1;
}
}
else low[x] = min(low[x], dfn[y]);
}
}
for what reason?p == 0 clarification\(x\) What about the root node? You must know that!
Because that's how it's written in the main function:
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i, 0);
tarjan Finding point bi-connected components
I should write first to seek point double good it or first to seek to cut the edge good it, both of them need to cut the point of the relevant knowledge, ah choice difficulties (
But, but, but.，After learning to find the cutoff point, then find the point double（acronyms BCC）It's easy. La La Little Fairy，Makabaka (name)，Kabalulu，fig. take on a new lease of life！
Algorithmic Thoughts:
Nature:A cut point in an undirected connected graph must belong to at least two BCCs and a non-cut point belongs to only one BCC
This is the diagram: point 2 is a cut point, the other points are not. There are two BCCs, red and blue.
There is one obvious conclusion:For every point double, the first point it finds at dfs must be a cut point or the root of the dfs tree。
Proof: it's obvious, right? According to the definition of the cut point to understand a little, do not prove. Forget it, or simply say it: we know that the cut point is the intersection of BCC, that is, BCC connected through the cut point, from one BCC to another BCC must start from passing through the cut point, so the proof.
Then this conclusion is actually equivalent toEach BCC is in the subtree of its first discovered point (a cut point or root node)The cut point is the point bi-connected component of the tree. Then every cut point (or root node) we find on the basis of the above method of finding cut points, its subtree (containing itself) is a point bi-connected component.
Realization:
We still maintain a stack, store points, whenever the search for a point into the stack, to find the cut point (that is, to find a BCC) will be the top of the stack to the cut point of all the elements in turn out of the stack, (but note: the cut point does not go out of the stack, because the above has said that a cut point belongs to the two BCCs, it also needs to come to update the other BCC, so the first does not go out of the stack, the special judgment on the line.) Then the elements out of the stack and the cut point is the desired point double.
Algorithm Demo:
As in the above figure, we start our search with 1 as the root;
When searching for node 2, continue recursion 2 -> 3 -> 4; find\(low_4 = 2 < dfn_3\)Then point 3 is not a cut point, backtracking;
(indicates contrast)\(low_3 = dfn_2\)So.\(2\) point is the cut point, then the stack will be divided at this point from the top of the stack to the\(2\) No. All elements of the point are out of the stack to form a point double;
The stack is now 1, 2, 3, 4 in order from the end of the stack to the top of the stack, so it is 2, 3, 4 that form a point double (but 2 is still on the stack).
Continuing to backtrack to 2 -> 1; we find that point 1 is the root node, and also take the elements of the stack out of the stack (at this point, 1 is the root node, so 1 is out of the stack as well), then 1, 2 form another point double.
Algorithm code:
void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x;
if(!p and !head[x]){ // special verdict for a solitary point
BCC[++bcc].emplace_back(x);
top--; return;
}
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(y == p) continue;
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x] or !p){ //is a cut point or root node
++bcc;
do BCC[bcc].emplace_back(s[top]);
while(s[top--] != y);
BCC[bcc].emplace_back(x);
}
}
else low[x] = min(low[x], dfn[y]);
}
}
Example question:
[Template] Point double connected component
Board questions to practice. Note that this question needs to determine the orphan point situation.
tarjan cut edge (bridge)
It's too easy!
It's about the same as cutting a point and changing a strip:low[y] > dfn[x], and there is no need to special-case the root node (since edge ! = point).
Explanation: (under the condition that the sentencing side ensures that there is no backtracking)\(low_y = dfn_x\) When this is the case, it means that it is not passed from the\(x -> y\) This path.\(y\) It's still possible to go back to\(x\) node, then it is guaranteed that the nodes from the\(y\) until (a time)\(x\) There are two paths to take now, so\(x->y\) This road is not a cut edge.
Then it's over!
Algorithm code:
cut[i] = true; indicate\(i\) This road is a cut edge.
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];
if(y == p) continue;
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] > dfn[x]){
cut[i] = true;
}
}
else low[x] = min(low[x], dfn[y]);
}
}
Topic Exercise:
Here's a good one. tarjan questionnaire, from templates to advanced, the questions are good and recommended.
The topics included are as follows
P1656 Bombing of railroads
P1455 Matching Purchases
P3916 Graph Iteration
P2835 Burning CD-ROMs
P1073 [NOIP2009 Improvement Group] Optimal Trading
P2863 [USACO06JAN] The Cow Prom S
P8436 [Template] Side Dual Connected Components
P8287 "DAOI R1" Flame
P2002 Message Diffusion
P2341 [USACO03FALL / HAOI2006] Popular Cow G
P3387 [Template] Shrink Point
P3388 [Template] Cutting Point (Cutting Top)
P8435 【Template】 Point Double Connected Component
P1407 [NCT] Stabilizing Marriage
P2194 HXY Burning Couple
P2746 [USACO5.3] Network of Schools
P2812 Network of Schools [[USACO] Network of Schools Enhanced Edition
P2941 [USACO09FEB]Surround the Islands S
P2860 [USACO06JAN]Redundant Paths G
P3398 [USACO09FEB]Hamster looking for sugar
P2169 Regular Expressions
P3627 [APIO2009] Looting program
P2656 Mushroom Picking
P4306 [JSOI2010] Connections
P5676 [GZOI2017] Little z plays games
P1656 Bombing the Railroad
P1455 Matching Purchase
P3916 Graph Iteration
P2835 Burning CD-ROMs
P1073 [NOIP2009 Improvement Group] Optimal Trading
P2863 [USACO06JAN] The Cow Prom S
P8436 [Template] Side Dual Connected Components
P8287 "DAOI R1" Flame
P2002 Message Diffusion
P2341 [USACO03FALL / HAOI2006] Popular Cow G
P3387 [Template] Shrink Point
P3388 [Template] Cutting Point (Cutting Top)
P8435 【Template】 Point Double Connected Component
P1407 [NCT] Stabilizing Marriage
P2194 HXY Burning Couple
P2746 [USACO5.3] Network of Schools
P2812 Network of Schools [[USACO] Network of Schools Enhanced Edition
P2941 [USACO09FEB]Surround the Islands S
P2860 [USACO06JAN]Redundant Paths G
P3398 [USACO09FEB]Hamster looking for sugar
P1262 The Spy Network
P4742 [Wind Festival] Running In The Sky
P8867 [NOIP2022] Building a Barracks
P3469 [POI2008] BLO-Blockade
P2515 [HAOI2010] Software Installation
P5058 [ZJOI2004]Sniffer
P7687 [CEOI2005] Critical Network Lines
P7924 "EVOI-RD2" Traveler
P5236 [Template] Static Cactus
P3225 [HNOI2012] Mine Building
P4716 [Template] Minimum Tree Chart
P4126 [AHOI2009] Minimum Cut
P6335 [COCI2007-2008#1] STAZA
P4637 [SHOI2011] Minesweeper Robot
P5236 [Template] Static Cactus
P4716 [Template] Minimum Tree Chart
P4436 [HNOI/AHOI2018] Games
End
After many days, I finally finished writing these two tarjan articles.
I've learned all about tarjan, so the next chapter of the package is going to be about rounded trees.
\(Stay tuned ...... \)