5/5/25, 10:00 AM Bridge Trees [Tutorial] - Codeforces
|
I_Love_HoangTrang | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
ARYAN12 BLOG TEAMS SUBMISSIONS GROUPS CONTESTS PROBLEMSETTING
aryan12's blog → Pay attention
Before contest
Bridge Trees [Tutorial] Codeforces Round 1023 (Div. 2)
[Link]
By aryan12, 3 years ago,
Before the tutorial, I would like to thank shiven, socho and animeshf for their valuable → Streams
comments and for improving the tutorial.
Codeforces Round 1023 (Div 2) —
Solution Discussion
Definition of Bridges By Shayan
Before stream [Link]
View all →
Bridges are those edges in a graph, which upon removal from the graph will make it
disconnected.
→ I_Love_HoangTrang
Pre-Requisites Rating: 1202
Contribution: 0
Finding the bridges in a graph. Settings
Blog
Favourites I_Love_HoangTrang
Introduction Teams
Submissions
Problemsetting
Groups
The idea of a bridge tree is to shrink the maximal components without a bridge into one node, Talks
leaving only the bridges of the original graph as the edges in the bridge tree. Contests
→ Top rated
# User Rating
1 tourist 3849
2 jiangly 3699
3 orzdevinwang 3695
4 jqdai0815 3682
5 maroonrk 3581
6 Benq 3546
7 Ormlis 3529
8 ksun48 3524
9 ecnerwala 3513
10 Radewoosh 3480
Countries | Cities | Organizations View all →
→ Top contributors
# User Contrib.
1 cry 162
2 Dominater069 160
3 Qingyu 158
3 -is-this-fft- 158
In the above image, the bridges of the graph are marked in red. They are the edges between the
5 atcoder_official 155
nodes (3, 4) and (3, 9) . The maximal components without a bridge are [1, 2, 3], [4, 5, 6, 7, 8],
[9, 10, 11, 12] . 6 djm03178 154
7 errorgorn 153
Thus, the bridge tree of the graph will become as follows:
8 adamant 152
9 luogu_official 151
10 soullless 143
View all →
[Link] 1/5
5/5/25, 10:00 AM Bridge Trees [Tutorial] - Codeforces
→ Find user
Handle:
Find
→ Recent actions
Mousa_Aboubaker → NAOI 2025 Teams
saiful_islam_bk → <h2><b> Divisor Sieve
</b></h2>
sunkuangzheng → Codeforces Round 1023
(Div. 2)
LelouchViBritannia_007 → I Give Up
Coderhype → IOI 2025
VladiG → How to become Master?
The bridge tree only has 3 nodes. The nodes [1, 2, 3] in the original graph have been shrunk to balllightning37 → Every CSES problem can
node 1, nodes [4, 5, 6, 7, 8] have been shrunk to node 2, and the nodes [9, 10, 11, 12] have be solved in 44 characters with Python
been shrunk to node 3. mrfunnyglassesman → How I Got LAST
Place in TSA Coding
Note: Throughout the tutorial, we assume that the given graph is undirected, unweighted and avighnakc → Efficient iterative segment tree
connected. with binary search
natnuo → Simple Codeforces Livestream
Software — TLE Live
Properties of the bridge tree avnithv → TJIOI Invitational Open in
Informatics (TJIOI) 2025
All the bridges of the original graph are represented as edges in the bridge tree.
atcoder_official → AtCoder Regular Contest
Proof 197 (Div. 2) Announcement
ch_egor → Pinely Round 2 Editorial
The bridge tree is connected if the original graph is connected.
bashkort → FAQ, Advice & AMA
Proof
ClosetNarcissist → WA in C++17 but AC in
C++23?
The bridge tree does not contain any cycles.
101rror → Is this the top problem solver on
Proof Codeforces?
mindflux → CodeSculptor88: The Legend,
The bridge tree will contain ≤ N nodes, where N is the number of nodes in the original graph. The Mystery, The OOP Overlord
Proof [Link] → Efficient and easy segment trees
The bridge tree will contain ≤ N − 1 edges, where N is the number of nodes in the original Acko → Mirror of Bubble Cup 13 Finals on
graph. Codeforces
Proof EduardoBrito → OII 2025 Teams
k1sara → Codeforces Round #1014 (Div. 2)
Pseudocode for making the bridge tree Editorial
Otherwordly → IOI 2025
dfs(int node, int component_number) { kostka → Baltic Olympiad in Informatics
2025
component[node] = component_number //All nodes with the same component number
MikeMirzayanov → Rule about third-party
will be shrunk into one node in the bridge tree. This is because we aren't
code is changing
traversing a bridge, and thus, "shrinking" the components without a bridge to one
[Link].2_0-0 → Codeforces
node in the bridge tree. Round 1022 Editorial
vis[node] = true //so that we don't visit this again.
for every adjacent edge such that the edge is not a bridge { Detailed →
next = other endpoint of the edge
if vis[next] = true: continue //already visited this node.
dfs(next, component_number);
}
}
main() {
Find all the bridges in the graph //check the pre-requisites section of this
blog for this
for i in 1, 2, 3, ..., n and vis[i] = false {
call dfs(i, unique_component_number) //ensure the component number is
unique. A simple way to do it is just by incrementing it by 1 whenever you are
calling the dfs function.
}
[Link] 2/5
5/5/25, 10:00 AM Bridge Trees [Tutorial] - Codeforces
The time complexity of making the bridge tree
In this section, N stands for the number of nodes and M stands for the number of edges in the
original graph. The bridges in the graph can be found in O(N + M ). The time complexity for the
DFS function is O(N + M ). Note that we can store the ID of the edge alongside the adjacent
node in the adjacency list. We can have an array isBridge , and mark isBridge[edge] =
true for every edge which is a bridge. During the DFS, just check if the current edge is marked
as a bridge using its stored ID.
Thus the total time complexity will be O((N + M ) + (N + M )) , which is equivalent to
O(N + M ) .
Sample problem
We are going to solve this problem.
Let us understand the statement first.
There is a connected, unweighted, undirected graph with N nodes and M edges.
According to the statement, for some fixed starting node s and ending node t , your friend will
place a boss in each passage such that it is impossible to travel from s to t without using this
passage. The word impossible tells us that the bosses can only be placed on bridges.
Why only on bridges?
Solution
Since we are only concerned regarding the bridges of the graph, we can compress all the
maximal components without a bridge into a single node to get the bridge tree of the graph. The
bridge tree of the first sample input is depicted below.
You can see that the nodes [1, 2, 3] in the original graph are shrunk to node 1 in the bridge tree.
Similarly, node [4] is shrunk to node 2 and node [5] is shrunk to node 3.
This makes the original problem a lot easier. The only thing left is to choose a path from one
node in the bridge tree to the other so that the number of edges (bridges in the original graph)
along the way is maximum. This can be solved by finding the diameter of a tree.
You can find my solution here.
Extra Exercise
Can you answer queries of the form find the number of bosses we need to place between fixed s
and t ?
[Link] 3/5
5/5/25, 10:00 AM Bridge Trees [Tutorial] - Codeforces
Other Problems
1. 652E, My solution
2. 555E, My solution
3. 231E
Feel free to suggest any other problems! I'll add them to this section.
bridge-tree, tutorial, tree, bridge, graphs
+127 aryan12 3 years ago 9
Comments (8) Show archived | Write comment?
3 years ago, # | +7
Amazing blog!
The blog by -is-this-fft- : [Tutorial] The DFS tree and its applications: how I found out
I really didn't understand bridges is an amazing blog on bridges.
It has the explanation to the problem: 231E — Cactus which can be solved using the
bridge tree approach.
Manan_shah
There a small correction too: in the pseudo-code, it should be dfs(next,
component_number);
→ Reply
3 years ago, # ^ | +1
Thanks a lot! Fixed the typo and added the problem.
→ Reply
aryan12
3 years ago, # | +4
Thanks for such a wonderful content
→ Reply
parth_kabra
3 years ago, # | ← Rev. 2 +4
Nice blog.
→ Reply
harshvardhan
3 years ago, # ^ | +4
Thanks.
→ Reply
aryan12
3 years ago, # | +4
I was solving the sample problem and I independently came up with the idea of
compressing a graph into a bridge tree. Lo and behold, I stumble upon this post that
validated my solution idea.
tgp07 → Reply
3 years ago, # ^ | 0
What is wrong with this comment? Why are people downvoting it?
→ Reply
aryan12
12 months ago, # | +7
Nice Blog'
You can add two problems
M0rdy
100676H - H. Capital City This one needs you to think greedy
100712H - Bridges This one is standard and easy to get the answer
I solved them by constructing a tree with myself as I didn't know there was
[Link] 4/5
5/5/25, 10:00 AM Bridge Trees [Tutorial] - Codeforces
I solved them by constructing a tree with myself as I didn t know there was
something called Bridge Trees
so my code will be so long but I will say what I use in it
use Tarjan for bridges to get bridge edges in the graph
then I build a graph using DSU with edges that do not bridges
then i mark for every connected component what is the min node in it (must
make this for the first problem)
after that, I build the tree with edges that are bridges but I make sure for every
node I get the minimum node in his CC
solutions:
my solution for the first problem Here
my solution for the second one Here
so long code but it's okay for me as I don't know this blog before
two problems are so good to solve
feel free to ask about anything in it
→ Reply
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/05/2025 [Link]UTC+7 (l3).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
[Link] 5/5
