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; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

计算机视觉著名数据集CV Datasets

Detection PASCAL VOC 2009 datasetClassification/Detection Competitions, Segm...

37480
来自专栏数据结构与算法

BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼哈顿距离)

有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家...

13040
来自专栏CreateAMind

Building Agents with Imagination

16830
来自专栏CreateAMind

视觉机械臂 visual-pushing-grasping

31410
来自专栏专知

ACL 2018 计算语言学协会接受论文列表

44910
来自专栏技术沉淀

Ruby练习二input: ['cars', 'for', 'potatoes', 'racs', 'four','scar', 'creams', 'scream']=> output: [["c

12950
来自专栏人工智能头条

将机器学习应用于金融技术领域的15家公司(英)

16420
来自专栏程序生活

第三周编程作业-Planar data classification with one hidden layerPlanar data classification with one hidden l

Planar data classification with one hidden layer Welcome to your week 3 programm...

1.3K100
来自专栏ml

HDUOJ -----1864 最大报销额(动态规划)

最大报销额 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

31940
来自专栏数据科学与人工智能

【陆勤践行】DataSchool 推荐的数据科学资源

Blogs Simply Statistics1: Written by the Biostatistics professors at Johns Hopki...

30590

扫码关注云+社区

领取腾讯云代金券