题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2503

思路题;

首先,这种问题应该注意到答案只跟度数有关,跟其他什么连接方法之类的完全无关;

关注最终状态,每个点度数都是2,所以对于原来度数不是2的需要进行处理;

也就是度数大于2的进行一次操作分成若干个2,如果是奇数那么留下一个1的等待合并,可以知道最终一定有偶数个度数为1的点;

然后考虑不是一个连通块的情况,需要把所有连通块变成链,再把它们连起来;

如果之前拆分过点,那么可以顺便多拆出两个度数为1的点,不损耗次数;

而如果原来就是一个欧拉回路,那么需要多拆一次;

然后合并,答案加上 度数为1的点数/2;

锻炼思路和码力啊!

参考TJ:https://blog.csdn.net/PoPoQQQ/article/details/48031135

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=;
int n,m,deg[maxn],fa[maxn],ans,sum,cnt;
bool split[maxn],odd[maxn];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<maxn;i++)fa[i]=i;//maxn!!
for(int i=,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
// if(!x){deg[y]++; continue;}
// if(!y){deg[x]++; continue;}
if(!x)x=++n;
if(!y)y=++n;
deg[x]++; deg[y]++; fa[find(x)]=find(y);
}
for(int i=;i<=n;i++)
{
if(deg[i]>)ans++,split[find(i)]=;
if(deg[i]%)sum++,odd[find(i)]=;;
if(find(i)==i&&deg[i])cnt++;//deg[i]!
}
for(int i=;i<=n;i++)
if(find(i)==i&&!odd[i]&&deg[i]&&cnt>)
{
sum+=;
if(!split[i])ans++;
}
printf("%d",ans+sum/);
return ;
}
05-14 20:18