罪世界-平行齿轮

Time Limit: 1000 ms   Memory Limit: 256 MB

Description

罪-平行齿轮作为“调整”，要为罪-真实龙出场做好铺垫。众所周知，罪-真实龙是用罪-平行齿轮与另一只罪世界的Oier组(he)合(ti)而成。为此，罪-平行齿轮要去Oier的家抓陈(zhang)立(kai)杰(jie)、范(zen)浩(bi)强(yang)等人送入罪世界。 象(zuo)征(wei)正(pan)义(tu)的你站了出来，你告诉了罪-平行齿轮Oier们共有n个房子，并打印出了连接这n个房子的m条路的信息。于是罪-平行齿轮决定从你家开始去亲切问候Oier们。罪-平行齿轮有强迫症，他不在乎能否抓到所有Oier，但他必须从你的家（编号为1的房子）开始，走完这m条路，还希望自己最后能回到你的家为行动画上一个圆满的句号。你清楚的知道在当前情况下很难满足罪-平行齿轮的要求，还会被罪-平行齿轮送会给陈(zhang)立(kai)杰(jie)与范(zen)浩(bi)强(yang)给用动态图与黑箱子砸死。 现在你只能用仅有的4个小时来写个程序，快速找出你至少要添加几条路才能满足：罪-平行齿轮从你的家开始，走完原来的m条路，并最后回到你的家。由于你过于大神，你只要知道最少要添加的路的数量就可以了

Input

输入一行两个整数n,m，意思如题目描述。 接下来m行，每行2个数x,y，表示编号为x的房子与编号为y的房子间有一条路。

Output

输出一行一个整数，表示最少要添加的路的数量。

Sample Input

2 5 1 1 1 2 1 2 2 2 1 2

Sample Output

1

HINT

对于30% 的数据，n,m≤1000

对于 100% 的数据，n,m≤106

注意：所有路都是无向的 !!!!!

题解：题意就是求一个图最少要加多少条边才能出现欧拉回路，所以将度数为奇数的点两两搭配加边即可。

那么我们只需输出这个图中度数为奇数的点的个数除以2。

代码：

#include <cstdio> using namespace std; int du[1000001],ans; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int a,b; scanf("%d%d",&a,&b); ++du[a]; ++du[b]; } for(int i=1;i<=n;++i) { if(du[i]%2) { ++ans; } } printf("%d\n",ans/2); }