把过程倒过来，相当于从所有边全黑开始，每次选一个邻边全黑的点，将它的一条邻边染白，使得最后黑色边最少。容易发现一个大小为 $x$ 的连通块可以染白 $x-1$ 条边，因此答案为 $m-$ 连通块数。时间复杂度 $O(n+m)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #351 for Problem #12216. Free Edges
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:15:08
Last updated: 2025-12-14 07:15:11
题解
Comments
No comments yet.