Hi, Codeforces!

A few days ago I discovered an interesting method for determining the cost of a second minimum spanning tree.

Problem statement

You're given a weighted graph with $$$n$$$ vertices and $$$m$$$ edges. You need to build two spanning trees: the first spanning tree must be the minimum and the second spanning tree also must have the minimum sum of edges, but the trees must differ by at least one edge (informally: the first is the MST (Minimum Spanning Tree) and the second is as close to the MST as possible).

I came across this task more than two years ago at an Olympiad programming courses. Back then, this task had small limits on $$$n$$$ and $$$m$$$, which supposed $$$O(nm\cdot\alpha(n))$$$ solution (where $$$\alpha$$$ is the inverse-Ackermann function).

Expected solution

First of all, let's sort the list of all edges by their cost and find the MST using Kruskal's algorithm. Since spanning trees differ by at least one edge, the second spanning tree must not contain at least one edge of the first one (otherwise they would be the same). So let's iterate through all the edges of the MST and for each edge we will assume that it isn't included in the second MST (thus, we will try to throw out $$$n - 1$$$ edges). Now we just need to mark this edge as useless and run 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). Thanks to this, we will find an MST without a specific edge. The cheapest of these spanning trees will be the second MST (because we tried to exclude every edge of the first MST).

Even then, it seemed strange to me that a task with such a simple formulation did not have a quick solution, so I started looking for it, but made a mistake that I could only realize recently (I could only find useful information about this task after I started writing a blog).

The best solution

However, before starting the solution, it is necessary to formulate an important lemma.

The second MST lemma

There exists a second MST such that it differs from the first by exactly one edge.

Thanks to D_ck for the proof of this lemma.

Due to the second MST lemma, we need to remove one edge and add one edge to the major MST to create the second MST from it. So let's invert the idea of the slow solution. Instead of searching for the edge that we should delete, we will search for the edge that we should add. Now, for every edge that is not included in the MST (their quantity is $$$m - n + 1$$$) we will suppose that it is included in the second MST. If we add this edge to the tree, it will form a cycle with path between the ends of our edge. This means that we must throw away any edge on this path. It's easy to make sure that the graph will remain connected. To minimize the increase in the cost of the tree, we need to remove the most expensive edge on this path (e.g. it could be found using binary lifting: you just need to precalculate the maximum edge weight on each jump and find the maximum on both halves of the path, divided by the LCA). Thus, the whole algorithm works in three steps.

• Step one. Find the MST by any method.
• Step two. Precalculate binary lifting with maximum edges on the spanning tree.
• Step three. Find the edge that increases the answer in the least possible way ($$$\Delta_{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 (The number of MSTs in a specific graph)

My friend showed me this task a few days ago, he found it in the qualification to the top division of one of the Russian competitive programming camps. And it really reminded me of the problem of the second MST and I finally solved it with the help of my friend after such a long time (that's why I decided to write about both promblems in this blog).

Problem statement

You're 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 second MST lemma (read the bold text in it), it's easy to understand that every MST has the same number of edges of a certain weight as the others (because every edge-change operation adds the same cost as it removes).

Now let's look at each weight independently. How many changes can we make with this weight? How many variants do these changes create? Let's consider all cases:

MST has 0 edges of this weight

We cannot change edges, because we just don't have them. 0 changes, 1 variant.

MST has 1 edge of this weight

We can change this edge to another, if it is possible. 0/1 change, 1/2/3 variants.

MST has 2 edges of this weight

We can change one of them to the remaining one, if it's possible. 0/1 change, 1/2/3 variants.

MST has 3 edges of this weight

We cannot change edges, because all three have already been taken. 0 changes, 1 variant.

But how can we find the number of variants for each weight? Well, let's hang our MST by any vertex, then run DFS from the root and record the entry and exit times for each edge (tin & tout for edges).

Now, for example, we want to check if the edge $$$e_1$$$ (from the MST) can be replaced by the edge $$$e_2$$$ (not from the MST). Let $$$v$$$ and $$$u$$$ be the ends of the edge $$$e_2$$$, and also let $$$e_v$$$ be the edge from the parent of $$$v$$$ to $$$v$$$ (the same with $$$e_u$$$). Then the edge $$$e_1$$$ can be replaced by the edge $$$e_2$$$, if $$$e_1$$$ is an ancestor of only one of the edges $$$e_v$$$ or $$$e_u$$$ (we can check, that one edge is an ancestor of the other, in the same way as we usually do for vertices, using entry and exit times, which we counted for each edge). You can draw some pictures to understand why this is true (this method also perfectly works for the edges $$$e_v$$$ and $$$e_u$$$, which are located on the same vertical path in the tree). You don't even have to find the LCA of $$$v$$$ and $$$u$$$!

Checking every change with the method described earlier, you can easily find the number of variants for each weight.

The last step. To find all the variants of forming an MST, you just need to multiply the number of variants for each weight. This means that any theoretically possible combination of edge swaps won't lead to a disconnected graph!

Time complexity: $$$O(m\log n)$$$.

Thank you for reading! I hope you enjoyed it!