自动搬运

查看原文

来自洛谷，原作者为

	complete_binary_tree 互关条件：有勾||O Fortuna velut luna statu variabilis……

搬运于2025-08-24 21:27:22，当前版本为作者最后更新于2025-05-21 15:02:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么有 7000 通过的题目的测试点是错完了的，我也很好奇呢。

下称度数为奇数的点为奇点，度数为偶数且非 $0$ 的点为偶点。

首先我们考虑对于一个连通图最少需要几笔画完。

我们每一笔肯定会形成一个路径，这条路径的中间节点（除开头结尾的节点）会被经过两次（进一次，出一次），那么这个节点的度数就会减少 $2$。

考虑开头、结尾节点。如果开头、结尾节点不一样，那么会单进（或单出），这个节点的度数会减少 $\bm1$；如果开头、结尾节点一样，路径会形成一个环，开头、结尾贡献在同一个点上，即这个点度数减少 $\bm2$。

所以每次最多让两个节点的度数减少 $1$（路径上其余减少 $2$）。

那么我们此时贪心地猜想每条路径可以把两个奇点变成偶点（如果没有奇点直接删一条欧拉回路就好了，证明详见 OI-WIKI），是不是只需要操作奇点个数除以 $2$ 次（即删完所有奇点）就什么都不剩了呢？

事实上这是正确的读者自证不难。证明：

由于图连通，所以每次一定可以找到一条连接两个奇点的路径并删除。然后图会变成一个或多个连通图，对每个连通图继续做即可。

那么删的时候可能会遇到以下情况：

1. 如果对几对奇点操作后，在剩下的奇点中，有一个奇点与其他奇点互不连通（或整个图只有 $1$ 个奇点）。

   即，有一个子图连通且有奇数个奇点，不合图的性质（一个图只可能有偶数个奇点），即不可能出现。

2. 如果删完所有奇点最后还会剩偶点。

   由于只有偶点的图是欧拉图（或者一些互不连通的欧拉图的并），而且对于每一个子连通图肯定有至少一个点被访问过（如果没有，就违反了原图是连通图的题设）。

   此时我们可以在经过这个偶点的那条路径上插入一条欧拉回路。由于欧拉回路起终点相同，所以并不会破坏路径的性质；而且欧拉图一定会有一个欧拉回路（证明见 OI-WIKI）。

所以可以做到删完奇点后啥也不剩。

所以我们只要对每个连通子图统计奇点个数再除 $2$ 就行了。

注意细节：

• 图不一定连通！！！

• 一个没有奇点的图可能都是偶点，也要走一次；

• 在判定上面那一条的时候注意孤立点不用走。

代码：

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
bool vis[maxn];
int n,m,u,w,v,f[maxn],ans = 0,cnt;
vector<int>e[maxn],tmp[maxn];
void dfs(int u,int&id){
    vis[u]=1,tmp[id].push_back(u);
    for(auto v:e[u])if(!vis[v])dfs(v,id);
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= m;i++)
	{
		scanf("%d%d", &u, &v);
		f[v]++;
	    f[u]++;
        e[u].push_back(v),e[v].push_back(u);
	} 
    for(int i=1;i<=n;++i)if(!vis[i])dfs(i,++cnt);
    for(int i=1;i<=cnt;++i){
        int tmpans=0,can=0;
        for(auto x:tmp[i]){if(f[x]&1)++tmpans;if(f[x])can=1;}
        tmpans/=2;
        if(!tmpans&&can)++tmpans;
        ans+=tmpans;
    }
	printf("%d", ans);
	return 0;
}