做网站用什么系统较好,wordpress安装网站无法,如何导出WordPress主题,建设一个社交网站需要多少钱题意描述
给你无向图的NNN个点和MMM条边#xff0c;保证这 条边都不同且不会存在同一点的自环边#xff0c;现在问你至少要几笔才能所有边都画一遍。#xff08;一笔画的时候笔不离开纸#xff09;
解析
无向图中#xff0c;若一个图是连通的#xff0c;且奇数度个数的…题意描述
给你无向图的NNN个点和MMM条边保证这 条边都不同且不会存在同一点的自环边现在问你至少要几笔才能所有边都画一遍。一笔画的时候笔不离开纸
解析
无向图中若一个图是连通的且奇数度个数的点不超过2个时必定可以一笔画完 否则一笔可以消灭两个奇数度点所以笔数为奇数度点个数/2 所以考虑所有连通块即可
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N4e5100;
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,pre;
}p[N*10];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt]{y,fi[x],-1};fi[x]cnt;return;
}
bool vis[N];
int ans,du[N];
void init(){memset(fi,-1,sizeof(fi));cnt-1;memset(vis,0,sizeof(vis));ans0;memset(du,0,sizeof(du));
}
int o;
void dfs(int x){vis[x]1;o(du[x]1);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!vis[to]) dfs(to);}return;
}
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifwhile(scanf(%d%d,n,m)!EOF){init();for(int i1;im;i){int xread(),yread();addline(x,y);addline(y,x);du[x];du[y];}for(int i1;in;i){if(!vis[i]du[i]){o0;dfs(i);if(o0||o2) ans;else anso/2;}}printf(%d\n,ans);}return 0;
}
