Readme

1489.Find-Critical-and-Pseudo-Critical-Edges-in-Minimum-Spanning-Tree

此题在基本的MST建树的操作上套了一层有意思的壳。

根据关键边的定义，如果删除了它，那么无法生成最初数值的MST。所以我们挨个试每条边，满足这个条件的就是关键边。我们将他们放入Set1.

伪关键边的定义是，如果删除了它，那么依然可以生成一棵最小数值的MST；但是如果如果用了它，也能生成一棵最小数值的MST。前者很好验证，就是Set1的补集。后者怎么验证呢？我们可以强迫在构建MST的时候使用这条边。如何最小程度地改动原来的MST生成代码来实现这个功能呢？考虑到排序后的edges数组的第一条边总是会被用到的，我们就把待考察的这条边放在edges数组的第一个，那么就可以保证在构建MST的时候用上它。如果生成的MST与之前的最小输出的相同，那么就符合后者的条件，放入Set2. 因此，Set2中那些不属于Set1的边，就是所求的第二类边。