Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Critical Connections in a Network
Bookmark
Brute Force
Tarjan
Input
4 nodes, 1 bridge
6 nodes, 1 bridge
5 nodes, chain (all bridges)
4 nodes, no bridges
Custom
n
=
4
,
connections
=
[[0,1],[1,2],[2,0],[1,3]]
each node:
disc
/
low
timer =
0
0
1
2
3
remove one connection at a time and retest
each node:
disc
/
low
timer =
0
0
1
2
3
remove one connection at a time and retest
each node:
disc
/
low
timer =
0
0
1
2
3
reach
2
through 0
each node:
disc
/
low
timer =
0
0
1
2
3
reach
3
through 1
each node:
disc
/
low
timer =
0
0
1
2
3
pop
1
, queue = []
each node:
disc
/
low
timer =
0
0
1
2
3
reach
2
through 0
each node:
disc
/
low
timer =
0
0
1
2
3
BFS from
2
each node:
disc
/
low
timer =
0
0
1
2
3
neighbor 3
not reached yet
each node:
disc
/
low
timer =
0
0
1
2
3
rebuild the adjacency list without it
each node:
disc
/
low
timer =
0
0
1
2
3
pop
0
, queue = [2]
each node:
disc
/
low
timer =
0
0
1
2
3
1 critical connection
(1,3)
algo
master
.
io
Step:
Find every bridge in this 4-node network by removing one connection at a time
0 / 73
Input
4 nodes, 1 bridge
6 nodes, 1 bridge
5 nodes, chain (all bridges)
4 nodes, no bridges
Custom
n
=
4
,
connections
=
[[0,1],[1,2],[2,0],[1,3]]
0 / 73
algo
master
.
io
Step:
Find every bridge in this 4-node network by removing one connection at a time
