HDU 3018 Ant Trip（欧拉回路）

题意：n个点，m条边。最少画几笔

题解：算算度数，并查集随便搞一搞就出来了

#include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; bool isfa[N];//是否是父亲  int n,ans; int in[2*N];//度数  int odd[N];//奇数结点  int findfa(int a) {     return f[a]==a?a:f[a]=findfa(f[a]); } void merge(int a,int b) {     int t1,t2;     t1=findfa(a);     t2=findfa(b);     if(t1!=t2)        f[t2]=t1; } void init() {     memset(in,0,sizeof(in));      memset(odd,0,sizeof(odd));     memset(isfa,false,sizeof(isfa));     for(int i=0;i<=N;i++)         {           f[i]=i;         }          ans=0; } int main() {     int m;     while(~scanf("%d %d",&n,&m))         {             init();                     for(int i=0;i<m;i++)                {                      int a,b;                      scanf("%d %d",&a,&b);                      in[a]++; in[b]++;                      merge(a,b);//初始化                 }             for(int i=1;i<=n;i++)             {                 int fa=findfa(i);                 if(!isfa[fa])                  {                      isfa[fa]=1;                  }                 if(in[i]%2==1)                 {                     odd[fa]++;                 }             }             for(int i=1;i<=n;i++)             {                 //联通图                  if(isfa[i]&&in[i])//in[i]==0 孤立点忽略                  {                  if(odd[i]==0)//欧拉回路 奇数度点0一笔画                   {                      ans++;                  }                  else                      {                         ans+=odd[i]/2;//不是欧拉回路                         //有2k个奇数点，需要画k笔                      }                 }             }                printf("%d\n",ans);         }     return 0; }