Readme

1579.Remove-Max-Number-of-Edges-to-Keep-Graph-Fully-Traversable

我们先考虑这样一个问题：给一个包含N个点的联通图，这个图里面有M条边（M最多可以是N*(N-1)/2个），问如何找出N-1条边，恰好将这N个点都联通。

针对这题的解法是：我们任意给一个M条边的排列（也就是说顺序无所谓），依次check这些边。如果这条边连接两个未联通的点，那我们就采用这条边，同时意味着这两个点以及与这两个点已经联通的那些点，就被联通在了一起。如果这条边连接了两个已经联通的点，显然这条边就是冗余的，我们就不采用。这样我们找到N-1条可以采用的边之后，任务就完成了。

思考一下上面的方法，如果我们找到了N-1条边，是否一定意味着N个点都联通了，是否会有某个点还没被联通？假设某个点X未被选中的这N-1条边联通，那么必然有一条连接X和另一点（比如说Y）的边e没有被选中。但是我们当初在查验e边的时候，没有选中它是因为认为它连接的两个点已经联通了，这就引发了矛盾。所以上述的方案是完备的，我们找到的这N-1条一定能联通这N个点。

然后我们回到这个问题。现在有三种类型的边。我们势必会优先使用第三种类型的边，希望第三种类型的边能够联通尽量多的点。可以想象，操作之后整个图变成了若干个割裂的联通块，但是每个联通块内部是最优联通的（也就是用了最少的边）。每个联通块内部，是可以让两个人都自由访问到的。

然后我们在此联通状态的基础上，逐步添加第一类的边直至让N个点都联通。这样满足了Alice能访问所有的点。

并行的，我们在之前的联通状态的基础上，逐步添加第二类的边直至让N个点都联通。这样满足了Bob能访问所有的点。

这三个步骤所选中的所有的边的数目，就是需要最少的、可让两个人都联通所有点的边。剩余的都是可以删除的冗余边。