Introduction
Hello, Codeforces! A few days ago, I discovered an interesting method for determining the cost of a second minimum spanning tree.
Problem Statement
You are given a weighted graph with $n$ vertices and $m$ edges. You need to build two spanning trees: the first must be the minimum, and the second must also have the minimum sum of edges, but at least one edge must be different (informally: the first is the MST, and the second is as close to the MST as possible).
Expected Solution
First, let's sort all edges by their cost and find the MST using Kruskal's algorithm. Since at least one edge of these spanning trees is different, the second spanning tree must not contain at least one edge of the first spanning tree. Therefore, we iterate through all the edges of the MST and assume that each edge is not included in the second MST (thus trying to throw out $n - 1$ edges).
Next, we simply need to mark this edge as useless and run the standard Kruskal's algorithm, which will skip the marked edge (we don't even have to re-sort edges because their order won't change). Thus, we will find an MST without a specific edge. The cheapest of these spanning trees will be the second MST.
Best Solution
Before starting the solution, it's essential to formulate an important lemma.
Greater MST Lemma
There exists a second MST such that it differs from the MST by exactly one edge.
Proof
Let $T_1, T_2, T_3, ... T_k$ be the spanning trees, such that: $T_i$ differs from $T_{i + 1}$ by removing the edge $r_i$ and adding the edge $a_i$. We can construct the second MST by considering every edge not in the MST and adding it to the tree, forming a cycle. We then must discard any edge on this path, specifically the most expensive edge (e.g., found using binary lifting).
Algorithm Steps
- Find the MST by any method.
- Precalculate binary lifting with maximum edges on the spanning tree.
- Find the edge that increases the answer in the least possible way ($\nabla_{ans} = e_{new} - e_{old}$).
Time Complexity
$O(m \log n) + O(n \log n) + O((m - n) \log n) = O(m \log n)$.
Bonus Content
Number of MSTs in a Specific Graph
You are given a weighted graph with $n$ vertices and $m$ edges, where each weight occurs no more than three times. You need to find the number of minimum spanning trees in this graph modulo $10^9+7$.
Solution
Thanks to the proof of the greater MST lemma, we can understand that every MST has the same number of edges of a certain weight. We can analyze each weight independently to find possible variations of changes.
The last step is to multiply the number of variants for each weight to find all variants of creating an MST.
Time Complexity
$O(m \log n)$.
Thank you for reading! I hope you enjoyed it!
Blogger's Review: This article provides a comprehensive breakdown of the construction process for the second minimum spanning tree, showcasing a concise solution to a complex problem through the integration of lemmas and algorithms. This approach offers significant insights into optimization algorithm design, warranting further exploration and practice.