题目大意：给定一张无向图，每次可以进行以下两种操作： 1.将一个点分裂成一些点，原先这个点连接的每条边任选一个新点进行连接 2.将两个度数为1的点合并为1个点 求将这个图变成一个环的最小操作次数
首先我们考虑拆 由于终态每个点度数最多为2，因此我们将每个度数大于2的点都拆成一些度数为2的点，如果有零头，留下一个度数为1的点 由欧拉通路的相关结论可知，按照这种拆法，一个有条链，一个全是偶度数点的连通块可以被拆成一个环 然后如果得到的连通块不只有一个，，拆掉所有的环。(当然如果一个环是由上一步拆分得到的，那么直接在上一步拆分中让其成为一条链即可) 最后把所有的链连起来得到一个环 注意数组别开小了
;int n,m,cnt/*接头个数*/,ans;int degree[M];Union_Find_Set{int fa[M],rank[M];int Find(int x){if(!fa[x]||fa[x]==x)return fa[x]=x;return fa[x]=Find(fa[x]);}void Union(int x,int y){x=Find(x);y=Find(y);if(x==y) return ;if(rank[x]>rank[y])swap(x,y);if(rank[x]==rank[y])++rank[y];fa[x]=y;}}int main(){using namespace Union_Find_Set;int i,x,y;cin>>n>>m;for(i=1;i<=m;i++){scanf(“%d%d”,&x,&y);if(!x) x=++n;if(!y) y=++n;degree[x]++;degree[y]++;Union(x,y);}for(i=1;i<=n;i++){if(degree[i]==0)continue;if(degree[i]&1){cnt++;flag[Find(i)]=true;}if(degree[i]>2){++ans;splited[Find(i)]=true;}}int temp=0;//连通块个数for(i=1;i<=n;i++)if(degree[i]&&i==Find(i))++temp;for(i=1;i<=n;i++)if(degree[i]&&i==Find(i)&&!flag[i]&&temp>1){cnt+=2;if(!splited[i])++ans;}ans+=cnt>>1;cout<<ans<<endl;return 0;}
第一个青春是上帝给的;第二个的青春是靠自己努力的
