题目描述
给出一张图，可以有两种操作：①把一个点拆成若干点，连在这个点上的边可以任意连到拆成的点上。②将两条边自由端熔融成一个点。求最少的操作数使得这张图变成一个简单环。
思路
还是一样，我们从最简单开始，如果图是一个连通图，那么我们考虑最后的简单环每个点的度均为2，所以我们计奇数点的个数为cnt1，度大于2的点的个数为cnt2，那么对于cnt2个点，我们都需要进行至少一次的熔断，接下来思考能如何进行最少的熔融次数使图变成一个简单环，由于奇数的存在，所以熔断之后必定仍然存在奇数点，因此以最少的次数消去奇数点至少要cnt1/2次（奇数点个数必定为偶数），答案即为cnt2+cnt1/2。
再复杂化，如果是由多个连通块构成，那么我们先要考虑把每个连通块都操作成一条链，再通过熔融操作连接起来，对于每个一个连通块，我们进行分类讨论：
①如果存在奇数点，那么就不用管，显然可以通过cnt2+（cnt1-2）/2变为一条链，再加上分摊到每个连通块的一个熔融连接操作，不改变操作次数。
②如果不存在奇数点，就需要造出两个度为1的点，cnt1要加2：
（一）如果存在度大于2的点，可以在熔断的时候分割成两个度为1的点
（二）如果不存在度大于2的点，就需要额外一次操作造出这样一个节点来完成分割，cnt2加1
剩下就是一些细节问题，由于点是可以乱搞的，重要的是边，所以孤立点不用考虑。判连通性时用并查集即可，注意初始赋值不是n，因为有0号节点存在，最多点数为m*2。
代码
#include <bits/stdc++.h> using namespace std; const int N=2100,M=55000<<1; struct Edge { int x,y; }e[M]; int fa[M]; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void f_union(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy)fa[fx]=fy; } int read() { int res=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();} return res*w; } int deg[M]; bool flag1[M],flag2[M]; int main() { int n,m; n=read();m=read(); for(int i=1;i<=m*2;i++) fa[i]=i; for(int i=1;i<=m;i++) { int x=read(),y=read(); if(!x)x=++n; if(!y)y=++n; e[i].x=x;e[i].y=y; deg[x]++;deg[y]++; f_union(x,y); } int sum=0; int cnt1=0,cnt2=0; for(int i=1;i<=n;i++) { if(deg[i]==0)continue ; if(find(i)==i)sum++; if(deg[i]&1) { cnt1++; flag1[find(i)]=1; } if(deg[i]>2) { cnt2++; flag2[find(i)]=1; } } if(sum>1) for(int i=1;i<=n;i++) if(deg[i]&&find(i)==i&&!flag1[i]) { cnt1+=2; if(!flag2[i])++cnt2; } printf("%d",cnt2+cnt1/2); return 0; }