欧拉回路（hdu3018）

刚学图论不久，看着别人的博客慢慢学了一点基础的，感觉还是有点力不从心，感觉图论的题好多长得都很像，什么太监算法（Tarjan）,Kosaraju，当然最基础的还是并查集。。。好了继续介绍这道题。。。。

题意：蚂蚁王国有n个城市（n个点），要求输入的是第a个城市可以到第b个城市（m个边），求最少画几笔覆盖全部边。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 #define m 100002

 int point[m];///每个强连通分量的端点

 int cnt;///计数

 int fa[m];///并查集的父亲节点

 int qiang[m];///强连通分量

 bool used[m];///记录有没有访问过

 int du[m];///度，如果是偶数的话+1，如果是奇数的话+=点数*1/2；

 void unit(int n)

 {

     cnt=;

     for(int i=;i<=n;i++)

     {

         point[i] = ;

         qiang[i] = ;

         fa[i]=-;

         used[i]=;

     }

 }

 int find(int x)

 {

     if(fa[x] >= )

     {

         fa[x]=find(fa[x]);

         return fa[x];

     }

     return x;

 }

 void Union(int a,int b)

 {

     int x1 = find(a);

     int x2 = find(b);

     if(x1 == x2)

         return ;

     int r1 = fa[x1];

     int r2 = fa[x2];

     if(r1 < r2)

     {

         fa[x2] = x1;

         fa[x1] += r2;

     }

     else

     {

         fa[x1]=x2;

         fa[x2] += r1;

     }

 }

 int main()

 {

     int n=,t=;

     int x=,y=;

     while(~scanf("%d%d",&n,&t))

     {

         unit(n);

         cnt=;

         for(int i=;i <= t;i++)

         {

             scanf("%d%d", &x , &y);

             du[x]++;

             du[y]++;

             Union(x , y);

         }

         for(int i=;i<=n;i++)

         {

             int f = find(i);

             if( !used[f] )

             {

                 used[f] = ;

                 qiang[cnt++] = f;

             }

             if(du[i]% == )

                 point[f]++;

         }

         int output=;

         for(int i=;i < cnt;i++)

         {

             if(du[qiang[i]] == )

                 continue;

             if(point[qiang[i]]==)

                 output++;

             else

             {

                 output += point[qiang[i]]/;

             }

         }

         printf("%d\n", output);

     }

 }