记录编号	72174	评测结果	AAAAAAAAAA
题目名称	游历校园	最终得分	100
用户昵称	饺子	是否通过	通过
代码语言	C++	运行时间	0.937 s
提交时间	2013-10-15 21:49:30	内存使用	16.43 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int lim=100011;
const int len=500055;
struct self{int x,y;}s[len*2];
int first[len*2],nxt[len*2];
int num[lim];
int m,n;
int tempn;
bool flag[lim]={0};
int z=0,a,ans;

int head,tail;
int q[lim];

void bfs(int i)
{
    head=tail=1;
    q[1]=i;
    int tot=0;
    if(num[i]%2==1)tot++;
    while(head<=tail)
    {
        for(int e=first[q[head]];e!=-1;e=nxt[e])
        {
            if(!flag[s[e].y])
            {
                flag[s[e].y]=1;
                tail++;
                q[tail]=s[e].y;
                if(num[s[e].y]%2==1)tot++;
            }
        }
        head++;
    }
    if(tot>2)z=z+(tot-2)/2;
}
        
        

int main()
{
    freopen("sent.in","r",stdin);freopen("sent.out","w",stdout);
    memset(first,-1,sizeof(first));
    memset(nxt,-1,sizeof(nxt));
    scanf("%d%d",&m,&n);
    for(a=1;a<=n;a++)
    {
        scanf("%d%d",&s[a].x,&s[a].y);
        if(s[a].x==s[a].y)continue;
        s[a+n].x=s[a].y;s[a+n].y=s[a].x;
        nxt[a]=first[s[a].x];first[s[a].x]=a;
        nxt[a+n]=first[s[a].y];first[s[a].y]=a+n;
        num[s[a].x]++;num[s[a].y]++;
    }
    for(a=1;a<=m;a++)
    if(!flag[a]&&num[a]>=1)
    {
        //cout<<"a="<<a;
        flag[a]=1;
        bfs(a);
        z++;
        //cout<<" z="<<z<<endl;
    }
    z--;
    cout<<z<<'\n';
    return 0;
}