#10108. 「一本通 3.7 练习 2」Ant Trip

 性质题：

如果一个连通块可以构成欧拉回路或者路径，显然一笔画完事

然后如果有多个奇数度的点，设奇数度的点为ans，显然我们会发现这个要画ans/2笔，（奇数度的点一定成对存在）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
const int M=1e5+5;
int fa[M],in[M],a[M],b[M];
int get(int x){
    if(fa[x]==0) return x;
    return fa[x]=get(fa[x]);
}
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        memset(in,0,sizeof(in));
        memset(fa,0,sizeof(fa));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        int cnt=0;
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d %d",&v,&u);
            in[v]++,in[u]++;
            u=get(u),v=get(v);
            if(u!=v) fa[v]=u;
        }
        for(int i=1;i<=n;i++){
            if(get(i)==i) cnt++;
        }
        for(int i=1;i<=n;i++){
            a[get(i)]++;
            if(in[i]%2==1) b[get(i)]++;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i]<=1) continue;
            else if(b[i]==0) ans++;
            else if(b[i]>0) ans+=b[i]/2;
        }
        printf("%d
",ans);
    }
    return 0;
}