Bridges
Graph searches find routes and shortest paths, and they can also find the edges a graph cannot do without. An edge of an undirected graph is a bridge when removing it leaves two vertices that were joined with no path between them. An edge on a cycle is not a bridge, because the rest of the cycle is a second route between its ends. If an edge lies on no cycle, it is a bridge, since any other route between its ends would close a cycle with it. CSES's Necessary Roads asks for every bridge of a connected graph.
A country has cities and two-way roads, and every city can reach every other. A road is necessary if, once it is removed, some two cities can no longer reach each other. Find every necessary road.
The first input line holds and . Each of the next lines holds two cities and joined by a road. No two roads join the same pair of cities, and no road joins a city to itself. Print the number of necessary roads , then the roads, in any order.
Constraints
Sample · Input
5 5 1 2 1 4 2 4 3 5 4 5
Output
2 3 5 4 5
In the sample, cities 1, 2 and 4 form a triangle, and a tail runs from city 4 to city 5 to city 3. Each road of the triangle has a way around it through the third city, so none of them is necessary. The road from 4 to 5 is the only link between the triangle and cities 3 and 5, and the road from 3 to 5 is the only link to city 3. Those two roads are the answer.
The direct method tests each road: remove it, search to see whether the graph is still connected, and put it back. Each search costs , and there is one search per road, so at the limits the work is
At a rough steps a second that is 600 seconds, and the time limit is one second.
Split the edges into tree edges and back edges
The faster method starts from a single depth-first search, so let's first see what one search tells us about the edges. To make the search easy to follow, we renumber the sample from 0 so that the search below reaches the cities in numeric order, and we call them villages to keep the two numberings apart. Cities 1, 4, 2, 5 and 3 become villages 0 to 4, so villages 0, 1 and 2 form the triangle and a tail runs from village 1 to 3 to 4. The roads are numbered 0 to 4, as in the table below.
Let's run a depth-first search from village 0 and number the villages in the order the search first reaches them. These numbers are the discovery times, written tin (time in). Trying each village's roads in order of their numbers, the search goes 0, 1, 2, back to 1, then 3 and 4, so tin = [0, 1, 2, 3, 4].
A road the search walks along to reach a new village is a tree edge, and the tree edges form the search tree, rooted at the start. Every other road is a back edge, and in an undirected graph a back edge always joins a village to one of its ancestors, never two separate branches.
To see why, take a road between and , and suppose the search reaches first. The search does not leave until it has read all of 's roads, this one included, so it discovers before leaving : either along this road, or earlier by a longer route out of . Until it leaves , the search only walks down from or from villages it reached from , so every village it discovers in that time lands in 's subtree. So is a descendant of .
| Road | Joins | Kind | Bridge? |
|---|---|---|---|
| 0 | 0 and 1 | tree edge | no |
| 1 | 1 and 2 | tree edge | no |
| 2 | 2 and 0 | back edge | no |
| 3 | 1 and 3 | tree edge | yes |
| 4 | 3 and 4 | tree edge | yes |
A back edge is never a bridge, because the tree path between its ends is a second route, so only tree edges need checking. Removing the tree edge from down to its child splits the search tree in two: 's subtree, and everything else. The graph stays connected exactly when some other road has one end inside 's subtree and the other outside it. Every other tree edge has both ends on the same side, so a road that crosses between the two sides must be a back edge, and a back edge joins a village to one of its ancestors.
So the tree edge from to is not a bridge exactly when some back edge starts inside 's subtree and lands on or above it.
In the example, road 2 starts at village 2, inside the subtrees of 1 and 2, and lands on 0. Together with the tree path 0, 1, 2 it closes a cycle, so roads 0 and 1 are not bridges. No back edge starts in the subtrees of 3 and 4, so roads 3 and 4 are bridges.
Compute the low value of each vertex
We found those by eye. In code, searching each tree edge's subtree separately would cost up to per edge, in all on a long path. Instead, we keep one number per vertex: how high in the tree its subtree can reach without the tree edge above it. A vertex higher in the tree is discovered earlier, so we measure height by discovery time, and smaller means higher. We call this number the low value.
Definition
is the smallest discovery time reachable from by going down zero or more tree edges and then taking at most one back edge.
To compute it, start with , the route that stays at . A back edge from to an ancestor gives the candidate . A child gives the candidate once its own search has finished, since anything its subtree reaches, reaches by going down to first. The low value is the smallest candidate:
Here ranges over the far ends of back edges from , and ranges over the children of . A child finishes before its parent, so the search completes the low values on its way back up.
Now we can test each tree edge. When the search returns from to its parent , is final. If , a back edge from 's subtree lands on or above it, which is a route around the edge from to . Otherwise there is no such route:
The test runs at each return, so one search checks every tree edge.
Compute discovery and low values by hand
- Enter 0 at time 0. Road 0 leads to 1, entered at time 1. Road 1 leads to 2, entered at time 2.
- At 2, road 1 is the road the search arrived by, so the search skips it. Road 2 leads to 0, discovered at time 0: a back edge, so .
- Return to 1. , so road 1 is not a bridge, and becomes 0.
- From 1, road 3 leads to the new village 3 (time 3), and from 3, road 4 leads to the new village 4 (time 4). Village 4 has no other road, so .
- Return to 3. , so road 4 is a bridge. stays 3.
- Return to 1. , so road 3 is a bridge.
- Return to 0. , so road 0 is not a bridge. Road 2 from 0 leads down to 2, which is finished; that back edge was already counted at 2.
Step through the search and the bridge test
Each village shows tin / low once the search enters it. A road turns solid when the search walks along it, dashed when it is a back edge, and red when the search comes back across it with .
The Add road 5 button joins 4 and 3 a second time. Stepping through again, the search reads the new road from 4 as a back edge to 3, becomes 3, and road 4 is no longer a bridge. Starting at another village changes the times, but not the bridges.
Skip the arriving road, not the parent village
Standing at , the search must not count the road back to its parent as a back edge. If it did, would always be at most and no road would ever be a bridge. The obvious way to avoid that is to skip the neighbour , but it fails when two roads join and .
Take two villages joined by two roads, n = 2, edges = [[0, 1], [0, 1]]. Removing either road leaves the other, so there is no bridge. A search that skips village 0 while standing at 1 ignores both roads, gets and reports road 0. The fix is to store each neighbour with its road id and skip only the id the search arrived by. The second road then counts as a back edge, , and no bridge is reported. Necessary Roads promises no repeated roads, but a graph that has them needs the road ids.
Find every bridge with an explicit stack
bridge_ids takes villages and the roads in input order and returns the ids of the bridges in ascending order. The program around it reads Necessary Roads, numbers the cities from 0 and prints each bridge's two cities.
The search keeps its own stack instead of recursing, because a path through all cities would nest calls. A frame holds a village, the id of the road that reached it and the position of the next road to read. While a village has roads left, the search reads the next one. When it has none, the search pops it and does the return step for its parent, now on top of the stack: it lowers the parent's low value and tests the road between them.
def bridge_ids(n, edges):
graph = [[] for _ in range(n)]
for edge_id, (a, b) in enumerate(edges):
graph[a].append((b, edge_id))
graph[b].append((a, edge_id))
tin, low = [-1] * n, [-1] * n
is_bridge = [False] * len(edges)
timer = 0
for start in range(n):
if tin[start] != -1:
continue
tin[start] = low[start] = timer
timer += 1
stack = [(start, -1, 0)]
while stack:
v, edge_in, i = stack[-1]
if i < len(graph[v]):
stack[-1] = (v, edge_in, i + 1)
w, edge_id = graph[v][i]
if edge_id == edge_in:
continue
if tin[w] == -1:
tin[w] = low[w] = timer
timer += 1
stack.append((w, edge_id, 0))
else:
low[v] = min(low[v], tin[w])
else:
stack.pop()
if stack:
parent = stack[-1][0]
low[parent] = min(low[parent], low[v])
if low[v] > tin[parent]:
is_bridge[edge_in] = True
return [i for i, found in enumerate(is_bridge) if found]
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = [(int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1) for i in range(m)]
found = bridge_ids(n, edges)
lines = [str(len(found))]
for i in found:
a, b = edges[i]
lines.append(f"{a + 1} {b + 1}")
print("\n".join(lines))On the sample the program prints 2, then the roads 3 5 and 4 5.
Deeper read: why not a recursive search
A recursive search makes one nested call per village on the current path, and Necessary Roads allows a path through all cities. Python stops at its default recursion limit of 1,000 calls, so the recursive version raises RecursionError on a chain of about 1,000 villages.
In C++ each call takes stack space: a recursive version of this search compiled with clang at -O2 used 112 bytes per call, about 11 MB on a path of villages, and crashed under the 8 MB default stack of macOS (Linux also defaults to 8 MB). The explicit stack is the same search with the call stack written out: a frame's next position is where a recursive call would resume its loop.
Correctness of the bridge test
When the search returns from to its parent , is the smallest discovery time that 's subtree reaches with at most one back edge, and the road from to is a bridge exactly when .
is complete at that moment: every child of has already returned, and every road out of has been read.
Worked example
Trace bridge finding on other graphs
The trace prints tin and low after each step, and the bridge ids found so far. On Doubled road, two parts, the search has to start again at village 2; road 2 is a bridge, while neither copy of the doubled road between 0 and 1 is one. Loop of four has no bridge at all, and on a path every road is one.
Enter village 0 at time 0. So far its subtree reaches only itself, so low[0] = 0.
Change the example input
Current result: [3,4]
Find the vertices whose removal disconnects the graph
Now that we can find the edges a graph cannot lose, let's ask the same question about vertices. Removing a vertex removes its edges too, so it can disconnect a graph that no single edge removal would. Necessary Cities asks for those vertices.
A country has cities and two-way roads, and every city can reach every other. A city is necessary if, once it and its roads are removed, some two of the other cities can no longer reach each other. Find every necessary city.
The input is as in Necessary Roads. Print the number of necessary cities , then the cities on one line, in any order.
Constraints
Sample · Input
5 5 1 2 1 4 2 4 3 5 4 5
Output
2 4 5
Such a vertex is a cut vertex, also called an articulation point. The sample is the network from Necessary Roads. Removing city 4 separates cities 1 and 2 from cities 3 and 5, and removing city 5 leaves city 3 alone, so the answer is 4 and 5. In the village numbering these are villages 1 and 3.
Test a vertex against each child's low value
The same tin and low values also find cut vertices. Take a vertex that is not the root of the search, and a child of . If
then no back edge from 's subtree lands above , so removing cuts that subtree off from the vertices above it. The test uses ≥ where the bridge test uses >. A back edge landing on itself is a route around the edge from to , but that route is gone once is. Conversely, if every child has , each child's subtree keeps a back edge to a vertex above , so removing disconnects nothing.
The root has nothing above it, so the test would pass there for every child. Instead, the root is a cut vertex exactly when it has two or more children in the search tree. A second child means the search came back to the root and still found an unreached vertex. Back edges join only ancestors and descendants, so no road joins the two branches, and removing the root separates them. With one child, the tree edges still connect everything else once the root is gone.
On the example, searched from village 0, village 1 passes the test through child 3, since , and village 3 passes through child 4, since . Searched from village 1, the search reaches 0 and 2, comes back to 1 and only then finds 3. The root has two children, so the root rule marks village 1.
Find every cut vertex
cut_vertices is bridge_ids with two changes in the return step: it counts the root's children instead of testing the root, and it tests every other vertex with ≥. A vertex can pass the test for several children, so the search keeps one flag per vertex and reports each once.
def cut_vertices(n, edges):
graph = [[] for _ in range(n)]
for edge_id, (a, b) in enumerate(edges):
graph[a].append((b, edge_id))
graph[b].append((a, edge_id))
tin, low = [-1] * n, [-1] * n
is_cut = [False] * n
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
children = 0
stack = [(root, -1, 0)]
while stack:
v, edge_in, i = stack[-1]
if i < len(graph[v]):
stack[-1] = (v, edge_in, i + 1)
w, edge_id = graph[v][i]
if edge_id == edge_in:
continue
if tin[w] == -1:
tin[w] = low[w] = timer
timer += 1
stack.append((w, edge_id, 0))
else:
low[v] = min(low[v], tin[w])
else:
stack.pop()
if stack:
parent = stack[-1][0]
low[parent] = min(low[parent], low[v])
if parent == root:
children += 1
elif low[v] >= tin[parent]:
is_cut[parent] = True
if children >= 2:
is_cut[root] = True
return [v for v in range(n) if is_cut[v]]
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = [(int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1) for i in range(m)]
found = cut_vertices(n, edges)
print(len(found))
print(" ".join(str(v + 1) for v in found))On the sample the program prints 2, then the cities 4 and 5.
Recall Why does equality save an edge but fail to save a vertex?
When , the child’s subtree has another edge back to the parent. That route bypasses the tree edge, so the tree edge is not a bridge. Removing the parent removes the tree edge and that other edge together, so the same equality makes a non-root parent a cut vertex.
Step through cut-vertex detection
This is the same widget in its Cut vertices mode. A village turns red when the search comes back to it from a child with , and at the root the widget counts children instead.
Stepping through from village 0 and then from village 1, the root rule marks village 1 only the second time. With road 5 added, road 4 stops being a bridge, but village 3 stays a cut vertex, because removing 3 still leaves village 4 alone.
Direct every edge so every vertex reaches every other
Our next problem also comes down to bridges. It asks whether a two-way network can be made one-way with every place still reachable from every other.
You get an undirected graph with nodes and edges, with no repeated edges and no edge from a node to itself. Choose a direction for every edge so that every node can reach every other node along the directions.
The input is and , then one edge , per line. Print each edge as for the direction from to , or IMPOSSIBLE if no choice works. Any valid answer is accepted.
Constraints
Sample · Input
3 3 1 2 1 3 2 3
Output
1 2 2 3 3 1
In the sample the three edges form a triangle, and directing them 1 to 2, 2 to 3 and 3 to 1 makes a cycle through all three nodes.
A bridge makes the task impossible: once it has a direction, the vertices on the side it points to can no longer get back across. A disconnected graph is impossible too. Every other graph has an answer, a fact known as Robbins' theorem, and the search we already have finds one: direct each edge the way the search first reads it.
With that rule, a tree edge points from parent to child, and a back edge points up, from the descendant to the ancestor, because the descendant reads it first. To see why, let a back edge join an ancestor to a descendant . The search reads 's edges one at a time and explores a whole child subtree to the end between two of them, so when it reaches this edge at , every descendant of found so far has finished. The edge is not a tree edge, so the search had already found , which means has finished and has already read the edge from its own side.
Deeper read: why every vertex then reaches every other
The root reaches every vertex down tree edges. For the way back, take any vertex other than the root, with parent . The edge from to is not a bridge, so
some vertex in 's subtree has a back edge to a vertex discovered before . Going down tree edges from to that vertex and up the back edge, we reach a vertex with a smaller discovery time, and from there we repeat. The discovery time keeps dropping, so the walk ends at the root, which has time 0.
Direct the edges during the search
orient_roads records each edge's direction the first time the search reads it, and returns an empty list for a bridge or an unreached vertex. Skipping every edge that already has a direction also skips the edge the search arrived by, since it was directed on the way down.
def orient_roads(n, edges):
graph = [[] for _ in range(n)]
for edge_id, (a, b) in enumerate(edges):
graph[a].append((b, edge_id))
graph[b].append((a, edge_id))
tin, low = [-1] * n, [-1] * n
directed = [None] * len(edges)
tin[0] = low[0] = 0
timer = 1
stack = [(0, 0)]
while stack:
v, i = stack[-1]
if i < len(graph[v]):
stack[-1] = (v, i + 1)
w, edge_id = graph[v][i]
if directed[edge_id] is not None:
continue
directed[edge_id] = (v, w)
if tin[w] == -1:
tin[w] = low[w] = timer
timer += 1
stack.append((w, 0))
else:
low[v] = min(low[v], tin[w])
else:
stack.pop()
if stack:
parent = stack[-1][0]
low[parent] = min(low[parent], low[v])
if low[v] > tin[parent]:
return [] # a bridge
if -1 in tin:
return [] # not connected
return directed
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = [(int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1) for i in range(m)]
directed = orient_roads(n, edges)
if not directed:
print("IMPOSSIBLE")
else:
print("\n".join(f"{a + 1} {b + 1}" for a, b in directed))On the sample the program prints the cycle 1 to 2 to 3 to 1, listed in input order rather than the official sample's order.
Strongly connected components
So far every graph has been undirected. When the roads are one-way, is reachable from when some route follows the arrows from to , and reachability is no longer symmetric. Two vertices are in the same strongly connected component (SCC) when each can reach the other. Each vertex belongs to exactly one component, because mutual reachability splits the vertices into separate groups: a vertex reaches itself, and if and reach each other and and reach each other, then and do too, through .
A game has planets and one-way teleporters. Two planets are in the same kingdom exactly when each can reach the other. Find the kingdom of every planet.
The input is and , then one teleporter , per line, which goes from planet to planet . Print the number of kingdoms , then a label from 1 to for each planet; any valid labelling is accepted.
Constraints
Sample · Input
5 6 1 2 2 3 3 1 3 4 4 5 5 4
Output
2 1 1 1 2 2
A kingdom is exactly an SCC. In the sample, planets 1, 2 and 3 form a cycle, 4 and 5 reach each other, and no teleporter leads from 4 or 5 back to the cycle. So there are 2 kingdoms, labelled 1 1 1 2 2.
Shrinking each component to a single vertex, and keeping an arrow wherever an edge joins two components, gives the condensation of the graph. The condensation has no cycle: a cycle of components would let every vertex in them reach every other, so they would have been one component. Because it has no cycle, its vertices can be listed so that every arrow points forward, which no graph with a cycle allows.
Find the components with one search
Tarjan's algorithm finds the components in one depth-first search, with discovery times and a low value as for bridges. It adds a second stack of waiting vertices: those discovered but not yet put in a component.
The low values follow the rules for bridges with two changes. The search follows each edge only in its own direction, so there is no arriving road to skip. And in a directed graph, an edge to an already discovered vertex need not lead to an ancestor: it can lead into a branch the search has already finished. So gives the candidate only while it is still waiting.
Call the first vertex the search enters in each component its head. When the search enters the head , the other vertices of its component are all undiscovered, and reaches each of them by a route that stays inside the component. The search does not leave until it has followed every route out of through undiscovered vertices, so it finds all of them first, and every vertex of a component lies in its head's subtree.
When the search leaves with
no edge from 's subtree reaches a waiting vertex discovered before , so is a head. Its component is together with every vertex pushed after that is still waiting: the vertices of 's subtree that a deeper head has not already taken. They sit together at the top of the waiting stack, with the lowest of them in the stack, so the search pops vertices until it has popped . When , reaches a waiting vertex discovered earlier. That vertex's head has not been left yet, so the head is an ancestor of and reaches down tree edges. So is in the head's component and keeps waiting.
The search can ignore an edge into a popped component because no route leads from that component back to a waiting vertex. By the time the search left the component's head, it had explored everything the head reaches, and an edge from the component to an earlier waiting vertex would have made the head's low value smaller than its discovery time. So the rest of the search runs as if the popped components had been deleted from the graph.
Each vertex is pushed and popped once, and each edge is read once, from the vertex where it starts, so the algorithm runs in .
Strongly connected components in the directed example
Take six villages and the one-way roads 0 to 1, 1 to 2, 2 to 0, 1 to 3, 3 to 4, 4 to 3, 4 to 5 and 2 to 5. The components are {0, 1, 2}, {3, 4} and {5}. The note under each village is tin / low after a search from village 0 that tries the roads in that order.
- component {0, 1, 2}
- component {3, 4}
- component {5}
Recall Can a vertex whose search has finished still be waiting?
Yes. In the graph 0 → 1, 1 → 0, 0 → 2, 2 → 1, visit 1 before 2. The search returns from 1 while 1 is still waiting for its head, 0. The later edge 2 → 1 must lower , because all three vertices reach each other. A test that counted only vertices whose search is still running would ignore that edge and put vertex 2 in a component of its own.
Trace Tarjan's algorithm and implement it
Let's trace the six-village example, searching from village 0:
- Enter 0, 1 and 2 at times 0, 1 and 2. All three are waiting. At 2, the road to 0 reaches a waiting village, so .
- From 2, the road to 5 enters 5 at time 3. Village 5 has no road out, so . Pop 5: the first component is .
- Back at 2, stays 0. Back at 1, .
- From 1, enter 3 at time 4 and 4 at time 5. The road from 4 to 3 reaches a waiting village, so . The road from 4 to 5 leads into a finished component, so the search ignores it.
- Back at 3, . Pop 4 and 3: the second component is .
- Back at 1 and then at 0, . Pop 2, 1 and 0: the last component is .
Label every vertex with its component
The listing uses the same explicit stack of frames as bridge_ids. A vertex is waiting exactly when it has been discovered and comp has no component for it yet, so the code tests comp[w] == -1 instead of keeping a separate flag.
def strongly_connected(n, edges):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
tin, low = [-1] * n, [-1] * n
comp = [-1] * n
waiting = []
timer = count = 0
for start in range(n):
if tin[start] != -1:
continue
tin[start] = low[start] = timer
timer += 1
waiting.append(start)
stack = [(start, 0)]
while stack:
v, i = stack[-1]
if i < len(graph[v]):
stack[-1] = (v, i + 1)
w = graph[v][i]
if tin[w] == -1:
tin[w] = low[w] = timer
timer += 1
waiting.append(w)
stack.append((w, 0))
elif comp[w] == -1:
low[v] = min(low[v], tin[w])
else:
stack.pop()
if stack:
parent = stack[-1][0]
low[parent] = min(low[parent], low[v])
if low[v] == tin[v]:
while True:
w = waiting.pop()
comp[w] = count
if w == v:
break
count += 1
return comp, count
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = [(int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1) for i in range(m)]
comp, count = strongly_connected(n, edges)
print(count)
print(" ".join(str(c + 1) for c in comp))On the sample the program prints 2, then the labels 2 2 2 1 1.
Components are numbered in the order they come off the stack. On the sample, planets 4 and 5 come off first, so the labels differ from the official ones; both are accepted.
As we saw, by the time a component comes off the stack, every component its edges lead into has already come off, so in this numbering every edge between components leads from a higher number to a lower one. Reading the components from the highest number down visits them in an order where every edge points forward.
Count the work in one search
- One search
time - Each village is entered once and each road is read twice, once from each end: steps at the Necessary Roads limits.
- Extra space
- Neighbour lists with road ids,
tin,lowand the search stack. - Remove each road and search
time - One full search per road, the first idea above.
Mistakes that report the wrong bridges
Using the cut-vertex test
low[v] >= tin[u]for bridges.- Where it breaks
- On the example it returns
[0, 3, 4]: , so road 0 is reported, but the loop 0, 1, 2 protects it. - The fix
- Bridges need the strict test,
low[v] > tin[u].
Starting the search only at village 0.
- Where it breaks
- For
n = 4, edges = [[0, 1], [1, 0], [2, 3]]the search never reaches villages 2 and 3 and returns[]instead of[2]. - The fix
- The outer loop starts a new search from every village that is not yet discovered.
Apply the separate test at the root
Testing the root like any other village when finding cut vertices.
- Where it breaks
- In the triangle
n = 3, edges = [[0, 1], [1, 2], [2, 0]], marks the root, and the result is[0]instead of[], yet removing any one village leaves the other two joined. - The fix
- Mark the root only when it has two or more children in the search tree.
Ignore edges into a finished component
Lowering
low[v]through a one-way road into a component that is already finished.- Where it breaks
- On the six-village map, the road from 4 to 5 would set . Then , so 3 is never popped on its own, and the result is
[1, 1, 1, 1, 1, 0]: two components, and , one short. - The fix
- Use
tin[w]only while is waiting, that is, whilecomp[w]is still -1.
Further reading
- Jeff Erickson (PDF)Algorithms, Chapter 6: Depth-first search(opens in a new tab)
Section 6.6 shows that each strong component fills part of one subtree of the search, with its first vertex at the top, and builds Tarjan’s algorithm from the low value; the chapter’s exercises work up to linear-time tests for bridges and cut vertices. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- cp-algorithmsFinding bridges in a graph in O(N+M)(opens in a new tab)
The same test written recursively, including several edges between the same two vertices.
- cp-algorithmsFinding articulation points in a graph in O(N+M)(opens in a new tab)
The cut-vertex test with and the separate rule for the root of the search.
- cp-algorithmsStrongly connected components and the condensation graph(opens in a new tab)
Kosaraju’s two-pass algorithm, Tarjan’s single search, and building the condensation graph.
- USACO Guide, AdvancedStrongly Connected Components(opens in a new tab)
Kosaraju’s and Tarjan’s algorithms with Planets and Kingdoms as the focus problem.
- USACO Guide, AdvancedBCCs and 2CCs(opens in a new tab)
Splitting a graph into the pieces left after removing every bridge, and into biconnected components around the articulation points.
- OI Wiki, in Chinese割点和桥 (Cut vertices and bridges)(opens in a new tab)
Cut vertices, then bridges without and with parallel edges, the case the road ids above handle.