CF1559D2 Mocha and Diana (Hard Version)
思路
以下，两图分别称为 A ， B
首先，来证明一个贪心策略：有能连的边就连，或者说连边不会影响最大值
考虑一种特殊情况，A 只有两个联通块，记为 x 和 y ， B 只有两个联通块
如果从 x 中选出任意一点都无法连接到 y 中任意一点，那么说明 x 中任意一点和 y 中任意一点在 B 中在一个连通块内
这样推得 B 仅有唯一联通块，矛盾
所以上述情况一定可以连一条边
有一个显然的东西，连一条边会让 A 和 B 的联通块个数同时减 1 ，所以不难发现如果有 A 或 B 有一边成树了，那么一定没有可以连的边了
那么现在假设 A 有 r 个联通块， B 有 c 个联通块
不妨假设 A 和 B 中点 1 所在的联通块分别为 pa , pb
那么，将 A 中除去 pa 之外的视为一个整体， B 中同理，就转换为了上面的特殊情况
于是按上述可以一直连边直到一边成为一棵树，这显然也是能连的边数的最大值
那么贪心策略得证
考虑实现
首先，贪心将所有能和 1 连的点连接
那么现在图上只有三类点，在 A 和 B 与 1 联通，仅在 A 与 1 联通，仅在 B 与 1 联通
首先发现，第一类点没任何用，它不能任何点相连
然后显然的，一个第二类点可以和任意一个第三类点相连，因为他们不在同一个联通块
于是就可以贪心的连接了
只是要注意，连接可能会使后两类点变为第一类点，判断一下就好
代码
//Nope