记录编号	462992	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	ImwaOuKur	是否通过	通过
代码语言	C++	运行时间	0.642 s
提交时间	2017-10-23 18:43:11	内存使用	9.09 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define re register int
#define N 100010
#define M 500010
int head[N],vis[N]={0},du[N]={0},cnt=0;
int n,m,ans=0;
struct node
{
    int v,nex;
} edge[M<<1];

void add_edge(int x,int y)
{
    cnt++;
    edge[cnt].v=y;
    edge[cnt].nex=head[x];
    head[x]=cnt;
    du[y]++;
}

void bfs(int st)
{
    queue<int> Q;
    int sum=0;
    Q.push(st);
    if(du[st]%2==1) sum++;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        for(int k=head[x];k!=-1;k=edge[k].nex)
        {
            int to=edge[k].v;
            if(vis[to]==0)
            {
                vis[to]=1;
                Q.push(to);
                if(du[to]%2==1)
                    sum++;
            }
        }
    }
    if(sum>2) ans+=(sum-2)>>1;
    return ;
}

int main()
{
    freopen("sent.in","r",stdin);
    freopen("sent.out","w",stdout);
    memset(head,-1,sizeof(head));
    int i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    for(i=1;i<=n;i++)
    {
        if(vis[i]==0 && du[i]>=1)
        {
            vis[i]=1;
            bfs(i);
            ans++;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}