CF1726D 题解

hcywoi · 2023-01-13 19:56:53 · 题解

Edge Split。

一开始 nt 了，以为红边为一颗树，蓝边为剩余边，蓝边就不会有环了。

假设有 n 个点，m 条边，且这些边没有出现环，那么连通块的数量为 n - m，因为不存在环，所以依次增加 m 条边，每条边都是连接两个连通块，也就是每条边都会使连通块数量减 1。

那么理论最小值就是 n\times 2-m。

本题这个理论最小值是可以取到的。

证明：

让这个理论最小值取到，那么必定蓝边和红边都没有构成环。

红边为这些边的生成树，蓝边为剩余边。

那么当 m = n + 2 时，蓝边的边数为 3，有可能构成环。

假设构成了环。

• 我们随便选一条环上的边，并将其归为红边。
• 将红边环上的一边且不是上述的边归为蓝边。

这样就没有环。

因为一个环上至少有 3 条边。

【实现】

生成树可以用并查集实现，即判断一条边的两个端点是否在一个集合，如果在一个集合就是蓝边，否则是红边。

断环也可以并查集，即先将选得第一条边加入并查集，然后枚举红边，如果一条边的两个端点在一个集合，那么这条边就是可选边。

时间复杂度：\mathcal O(n\alpha(n))。

具体实现见代码。