Update second_best_mst.md

erikoui · adamant-pwn · commit 230b5c22ace4 · 2023-01-08T17:07:25.000+01:00
I was following the text description and couldn't figure out the cycle part(step 2). I hope this small note helps other people like me.
diff --git a/src/graph/second_best_mst.md b/src/graph/second_best_mst.md
@@ -37,8 +37,8 @@ Here we will do the exact opposite.
 We try to add every edge that is not already in the MST.
 
 1. Sort the edges in $O(E \log E)$, then find a MST using Kruskal in $O(E)$.
-2. For each edge $e$ not already in the MST, temporarily add it to the MST, creating a cycle.
-3. Find the edge $k$ with maximal weight in the cycle that is not equal to $e$.
+2. For each edge $e$ not already in the MST, temporarily add it to the MST, creating a cycle. The cycle will pass through the LCA.
+3. Find the edge $k$ with maximal weight in the cycle that is not equal to $e$, by following the parents of the nodes of edge $e$, up to the LCA.
 4. Remove $k$ temporarily, creating a new spanning tree.
 5. Compute the weight difference $\delta = weight(e) - weight(k)$, and remember it together with the changed edge.
 6. Repeat step 2 for all other edges, and return the spanning tree with the smallest weight difference to the MST.
