Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Find Critical and Pseudo-Critical Edges in MST
Bookmark
Brute Force
Kruskal Edge Testing
Input
LeetCode Example
All Pseudo-Critical
Path (All Critical)
Custom
n
=
5
,
edges
=
[[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Setup
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Setup
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
-
1
(1-2)
1
-
2
(2-3)
2
-
3
(0-3)
2
-
4
(0-4)
3
-
5
(3-4)
3
-
6
(1-4)
6
-
Enumerate MSTs | Baseline MST Weight: 7
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
Graph
1
1
2
2
3
3
6
0
1
2
3
4
Edge Classification
Idx
Edge
Wt
Classification
0
(0-1)
1
Critical
1
(1-2)
1
Critical
2
(2-3)
2
Pseudo-Critical
3
(0-3)
2
Pseudo-Critical
4
(0-4)
3
Pseudo-Critical
5
(3-4)
3
Pseudo-Critical
6
(1-4)
6
Neither
Complete | Baseline MST Weight: 7
Critical: [0, 1]
Pseudo-Critical: [2, 3, 4, 5]
Legend:
Testing
In MST
Critical
Pseudo-Critical
Default
algo
master
.
io
Step:
Look for spanning trees among the 7 edges, taking 4 at a time
0 / 532
Input
LeetCode Example
All Pseudo-Critical
Path (All Critical)
Custom
n
=
5
,
edges
=
[[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
0 / 532
algo
master
.
io
Step:
Look for spanning trees among the 7 edges, taking 4 at a time
