参考博客：

参考：

 题意：给你无向图的 N 个点和 M 条边，保证这 M 条边都不同且不会存在同一点的自环边，现在问你至少要几笔才能所有边都画一遍。（一笔画的时候笔不离开纸）

思路：先并查集将无向图的每个连通图分开，同时将所有点的度算一遍，

原图应是由若干个无向连通图组成的

当这个无向连通图只有一个点时，这是一个孤立点，不做操作，也就是只有一个点时特判

否则：计算每个无向图的奇度点的个数（可以通过find操作，将个数存在每个图集的代表点处，也就是find处）

　　 

如果奇度点的个数为0，表示是欧拉回路

　　如果奇度点的个数>=2，表示是对应的欧拉路径（欧拉回路也是欧拉路径）

　　所以：　  对欧拉路径 ：笔画数=奇度点数 / 2

　　　　　对欧拉回路：笔画数=等于1 

WA点：单点图要特判掉，虽然它也是欧拉回路，但是无边，对此题来说不需要安排蚂蚁去

无向连通图奇度点个数不可能为奇数

代码：

1 ***********************************************/ 2 int in[maxn],out[maxn]; 3 int st[maxn]; 4 int V[maxn]; 5 int num[maxn];  6     int n,m; 7  8 int find(int t) 9 {10     while(st[t]!=t) t=st[t];11     return t;12 }13 14 void add(int a,int b)15 {16     int fa=find(a);17     int fb=find(b);18     if(fa>fb) st[fa]=fb;19     else st[fb]=fa;20 }21 22 int main()23 {24 25     while(cin>>n>>m)26     {27         mem0(in);28         mem0(V); 29         mem0(st);30         mem0(num);31         for(int i=1;i<=n;i++) st[i]=i;32         for(int i=1;i<=m;i++)33         {34             int a,b;35             sc2(a,b);36             in[a]++;37             in[b]++;38             add(a,b);39         }40         int ans=0;41         for(int i=1;i<=n;i++) 42         {43             if(in[i]%2) V[find(i)]++;//奇数度的个数 44             num[find(i)]++;45         }46         for(int i=1;i<=n;i++) 47         {48             if(st[i]==i)49             {50                 //当是1个点的时候，特判51                 if(num[i]==1) continue;//因为一个点的图没有边 52                 if(V[i]>=2) ans+=(V[i]/2);53                 else ans++;//是欧拉回路 54             }55         }56         cout<
       
        <
       

 关于欧拉与哈密：