Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Maximize Spanning Tree Stability with Upgrades
Bookmark
Brute Force
Binary Search
Input
5 Nodes, 1 Must-Edge, k=2
Must-Edge Caps the Answer
All Optional, k=2
Must-Edges Form a Cycle (-1)
Custom
n
=
5
,
edges
=
[[0,1,6,1],[1,2,3,0],[2,3,4,0],[3,4,2,0],[0,4,5,0],[1,3,1,0]]
,
k
=
2
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: -
Edges upgraded: - / 2
Edges placed: - / 4
Weakest in tree: -
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
4
8
no
-
3-4
2
4
no
-
0-4
5
10
no
-
1-3
1
2
no
-
Status
k = 2
mustMin = -
Best = 0
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: -
Edges upgraded: - / 2
Edges placed: - / 4
Weakest in tree: -
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
4
8
no
-
3-4
2
4
no
-
0-4
5
10
no
-
1-3
1
2
no
-
Status
k = 2
mustMin = -
Best = 0
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 1
Edges upgraded: 1 / 2
Edges placed: 2 / 4
Weakest in tree: 6
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
6
6
no
In tree (2x)
2-3
4
8
no
-
3-4
2
4
no
-
0-4
5
10
no
-
1-3
1
2
no
-
Status
k = 2
mustMin = 6
Best = 3
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 3
Edges upgraded: 2 / 2
Edges placed: 2 / 4
Weakest in tree: 6
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
6
6
no
Doubled
2-3
8
8
no
In tree (2x)
3-4
2
4
no
-
0-4
5
10
no
-
1-3
1
2
no
-
Status
k = 2
mustMin = 6
Best = 4
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 5
Edges upgraded: 2 / 2
Edges placed: 2 / 4
Weakest in tree: 6
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
6
6
no
In tree (2x)
2-3
4
8
no
-
3-4
4
4
no
Doubled
0-4
5
10
no
-
1-3
1
2
no
-
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 8
Edges upgraded: 1 / 2
Edges placed: 2 / 4
Weakest in tree: 6
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
4
8
no
-
3-4
2
4
no
-
0-4
10
10
no
In tree (2x)
1-3
1
2
no
-
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 10
Edges upgraded: 2 / 2
Edges placed: 2 / 4
Weakest in tree: 6
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
8
8
no
Doubled
3-4
2
4
no
-
0-4
10
10
no
In tree (2x)
1-3
1
2
no
-
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 16
Edges upgraded: 1 / 2
Edges placed: 4 / 4
Weakest in tree: 4
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
4
8
no
-
3-4
2
4
no
-
0-4
5
10
no
-
1-3
2
2
no
Doubled
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 18
Edges upgraded: 2 / 2
Edges placed: 4 / 4
Weakest in tree: 4
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
8
8
no
Doubled
3-4
2
4
no
-
0-4
5
10
no
-
1-3
2
2
no
Doubled
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 20
Edges upgraded: 2 / 2
Edges placed: 4 / 4
Weakest in tree: 4
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
-
2-3
4
8
no
In tree
3-4
4
4
no
In tree (2x)
0-4
5
10
no
In tree
1-3
2
2
no
Doubled
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
Graph
6
3
4
2
5
1
0
1
2
3
4
Upgrade Subsets
Subset mask: 31
Edges upgraded: 5 / 2
Edges placed: 4 / 4
Weakest in tree: 3
Each subset doubles a different set of optional edges,
then rebuilds the maximum spanning tree from scratch.
Edges
Edge
s
2s
Must
Status
0-1
6
12
yes
Must
1-2
3
6
no
In tree
2-3
4
8
no
In tree
3-4
2
4
no
-
0-4
10
10
no
In tree (2x)
1-3
2
2
no
Doubled
Status
k = 2
mustMin = 6
Best = 5
Legend:
Must-edge
In tree
Doubled
Rejected
algo
master
.
io
Step:
n = 5, 6 edges (1 must-include), k = 2 upgrades. Try every set of upgrades and keep the best spanning tree.
0 / 198
Input
5 Nodes, 1 Must-Edge, k=2
Must-Edge Caps the Answer
All Optional, k=2
Must-Edges Form a Cycle (-1)
Custom
n
=
5
,
edges
=
[[0,1,6,1],[1,2,3,0],[2,3,4,0],[3,4,2,0],[0,4,5,0],[1,3,1,0]]
,
k
=
2
0 / 198
algo
master
.
io
Step:
n = 5, 6 edges (1 must-include), k = 2 upgrades. Try every set of upgrades and keep the best spanning tree.
