英文外贸网站 php源码,动漫设计好找工作吗,长沙网站建设推广服务,南通seo网站优化软件解析 本题是一道if的板子题 抓住关键#xff1a;使所有点的度数全变为2 首先对于度数大于2的点#xff0c;把它分为若干2度点#xff08;和可能的一个单点#xff09; 现在我们只剩下单点和二度点了
接下来分来讨论一下 若有多个连通块#xff0c;我们要把它们变成链再拼…解析 本题是一道if的板子题 抓住关键使所有点的度数全变为2 首先对于度数大于2的点把它分为若干2度点和可能的一个单点 现在我们只剩下单点和二度点了
接下来分来讨论一下 若有多个连通块我们要把它们变成链再拼起来 所以我们要把所有连通块的各自的单点拚到只剩下一个 最后把所有链拼起来
若只有一个连通块把所有的1度点合并即可
对于0的处理开一个新点
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e51050;
const double eps1e-6;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return f*x;
}
int n,m;
struct node{int to,nxt;
}p[N*10];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt]{y,fi[x]};fi[x]cnt;return;
}
int du[N];
int ans,num;
bool vis[N],f;
void dfs(int x){if(vis[x]) return;vis[x]1;if(du[x]2) ans,f1;num(du[x]1);for(int ifi[x];~i;ip[i].nxt){int top[i].to;dfs(to);}return;
}
int sum,flag,flag2;
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread();for(int i1;im;i){int xread(),yread();if(!x) xn;if(!y) yn;du[x];du[y];addline(x,y);addline(y,x);}for(int i1;in;i){if(!vis[i]du[i]){num0;f0;flag;dfs(i);if(num0)ans(num)/2-1;else ansf?0:1;}}if(flag1){if(num0)ans-(num)/2-1;else ans-f?0:1;ansansnum/2;}if(flag1) ansflag;printf(%d\n,ans);return 0;
}
/*
4a
1 2
2 3
1 3
3 4
*/
