严格次小生成树
前置芝士
定义
如果最小生成树选择的边集是 \(E_M\)，严格次小生成> 树选择的边集是 \(E_S\)，那么需要满足：(\(value(e)\) 表示边 \(e\) 的权值) \(\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)\)。
也就是说，严格次小生成树的边权和一定是比最小生成树的边权和要小，且是其它生成树中最大的。
题目
我们先来看一道例题
P4180 [BJWC2010] 严格次小生成树
求出无向图中的严格次小生成树
数据中无向图不保证无自环。
对于 \(100\%\) 的数据， \(N\le 10^5\)，\(M\le 3\times10^5\)，边权 \(\in [0,10^9]\)，数据保证必定存在严格次小生成树。
解决办法
题目中 \(n\) 和 \(m\) 的值很大，肯定不能暴力枚举出每个生成树。
但是我们仔细思考一下，严格次小生成树或许就是最小生成树中删去某一条边再添加另一条边得到的。
正向枚举删掉的边貌似不好处理，我们可以反向枚举添加的那条边。
那我们该怎么判断删掉那条边呢？仔细思考，我们可以得知一个信息：添加一条边后，这棵树就出现了环，我们只要删去环上的权值最大的一条边即可。
但是这样还会出现一个问题，就是如果最大的边和添加的这条边边权相同怎么办？(如图)
