蚂蚁之旅

【题目描述】：

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

【输入描述】：

多组数据，每组数据用空行隔开。

对于每组数据，第一行两个整数N,M表示点数和边数。接下去M行每行两个整数a,b ，表示a,b之间有一条边。

【输出描述】：

对于每组数据，输出答案。

【样例输入】：

3 3 1 2 2 3 1 34 2 1 2 3 4

【样例输出】：

1 2

【时间限制、数据范围及描述】：

时间：1s 空间：64M

1<=N<=10^5；0<=M<=2×10^5；1<=a,b<=N

 

#include<cstdio> #include<iostream> using namespace std; const int maxv=100000 + 2; int ch[maxv]; int du[maxv]; int p[maxv]; bool used[maxv]; int kkksc03[maxv]; void init(int n){for(int i=0;i<=n;++i){ch[i]=0;p[i]=-1;du[i]=0;used[i]=0;} }int find(int x){if(0<=p[x]){p[x]=find(p[x]);return p[x];}return x; }void un(int a, int b){int r1=find(a);int r2=find(b);if(r1==r2){return;}int n1=p[r1];int n2=p[r2];if(n1<n2){p[r2]=r1;p[r1]+=n2;}else{p[r1]=r2;p[r2]+=n1;} }int main(){int n=0;int m=0;int a=0;int b=0;int i=0;int cnt=0;while(scanf("%d%d",&n,&m)!=EOF){init(n);cnt=0;for(i=1;i<=m;++i){scanf("%d%d", &a, &b);du[a]++;du[b]++;un(a, b);}for(i=1;i<=n;++i){int f=find(i);if(!used[f]){used[f]=1;kkksc03[cnt++]=f;}if(1==du[i]%2){ch[f]++;}}int ret=0;for(i=0;i<cnt;++i){if(0==du[kkksc03[i]]){continue;}if(0==ch[kkksc03[i]]){++ret;}else{ret+=ch[kkksc03[i]]/2;}}printf("%d\n",ret); }return 0; }

 

转载于:https://www.cnblogs.com/hrj1/p/11186130.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的蚂蚁之旅的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。