Can anybody explain me how to find the second minimum spanning tree in the fastest way, I heard about disjoint sets I studied them but I still can't find the way to do it...

# | User | Rating |
---|---|---|

1 | Benq | 3797 |

2 | tourist | 3723 |

3 | Radewoosh | 3720 |

4 | ecnerwala | 3579 |

5 | ksun48 | 3463 |

6 | Um_nik | 3457 |

7 | maroonrk | 3446 |

8 | jiangly | 3432 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 184 |

2 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

6 | maroonrk | 176 |

6 | Radewoosh | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 169 |

Can anybody explain me how to find the second minimum spanning tree in the fastest way, I heard about disjoint sets I studied them but I still can't find the way to do it...

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2021 17:00:12 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

discard minimum cost & run MST code again.

I guess follow solution can be correct.

build MST. Then build a tree from edges of MST. Now if you try to add any other edge into a tree it makes a cycle in the new graph. find the edge with the maximal cost on the cycle and remove it from graph. Now graph is a tree again. Try all edges and choose the minimal possible tree (make shure it is not another MST). you can find maximal edge on the cycle in LogN using LCA(LeastCommonAncestor) and some other data structures.

O(M logN) for Kruskal and O(M logN) again for M queries with LCA. It will work.

thank you, I also came up with the idea of disjoint-sets to check if there is a cycle. Anw thanks everybody for helping.

First off, build the minimum spanning tree, then, for each edge of the minimum spanning tree, build a new one discarding such edge. The minimum one will be the second minimum spanning tree. Using Kruskal algorithm and a O(n * log(n)) sorting algorithm for the edges, this strategy lead to a O(N^2 * log(N)) overall complexity.

You can make use of the LCA algorithm and the observation that the second mst will differ from the first by only one edge to make the algorithm described by aajjbb run in O( ElogV ) time

Could you please provide some code for this O(ElogV) algorithm ?

You can read here

We can achieve this in O(E * log(N)) time using heavy-light decomposition. E = Number of Edges You can find more about heavy light decomposition here : Heavy Light Decomposition

Basically for every edge which you consider to add into the MST(Minimum Spanning Tree) to make it second minimum spanning tree, let us say it connects two vertices A and B.

Now after adding this new edge we need to remove one edge which is the smallest among the edges that lie in the path between A and B in the original MST. This can be achieved using Heavy Light Decomposition on the MST in Log(N) time for one edge. So it takes O(E * Log(N)) total time.

Source: https://www.quora.com/How-do-I-get-a-second-minimum-spanning-tree (Answer by adurysk)

Your general idea is correct, though you need to remove the largest edge on the path from A to B, not the smallest one. And also, you can achieve that without heavy-light decomposition. Two LCA-like data structures will solve it (one for ancestors, one for maximum edges).