本文主要是介绍uoj 117 欧拉回路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.判断是否为欧拉存在欧拉回路---裸的判断
欧拉回路就是看一笔能不能把途中所有的边跑完没得重复
对于无向边----建立双向边判断每个点的入度是否为2的倍数 1.1
对于有向边---建立单向边判断每个点的入度与出度是否相等 1.2
然后就是看一下是否所有的点是否连接----可以用并查集或者dfs判断，具体看情况来定。 2
判断是否存在欧拉回路，就是同时满足上边的1，2两个条件
HDU 1878代码 并查集 条件1.1+2
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
using namespace std;
const int maxn=1005;
int f[maxn],vis[maxn];
int n,m;
void init()
{for(int i=1;i<=n;i++){vis[i]=0;f[i]=i;}
}
int find(int x)
{if(x==f[x]) return x;else return f[x]=find(f[x]);
}
void unionn(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy)f[x]=y;
}
int main()
{int x,y;while(cin>>n,n){cin>>m;init();for(int i=1;i<=m;i++){scanf("%d %d",&x,&y);unionn(x,y);vis[x]++;vis[y]++;}bool flag=true;int cnt=0;for(int i=1;i<=n;i++){if(f[i]==i)cnt++;}if(cnt>1)flag=false;else{for(int i=1;i<=n;i++)if(vis[i]%2==1){flag=false;break;}}if(flag)printf("1\n");elseprintf("0\n");}return 0;
}2。输出欧拉回路 uoj 117
分两种情况建立单向或者双向边
判断1.1 or 1.2 ,然后用dfs来进行遍历，如果能够遍历所有的边，那么输出即可
但是这道题的数据很大很坑，存在的问题就是可能会出现自环，比如给了10000组的 1 1边，那么dfs的时候遍历是会超时的，利用邻接表的性质进行优化
代码如下
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const double pi=acos(-1.0);
const double E=2.718281828459;
using namespace std;
const int maxn=1e5+5;
const int maxm=2e5+5;
struct node
{int to,p,vis;
}edge[maxm<<1];
int n,m;
int in[maxn],out[maxn];
int head[maxn],sign,cnt;
void add(int u,int v)
{edge[++sign]=node{v,head[u],0};head[u]=sign;
}
void init()
{cnt=sign=0;memset(head,-1,sizeof(head));for(int i=1;i<=n;i++)in[i]=out[i]=0;
}
int ans[maxm];
void dfs_unedge(int u)
{for(int i=head[u];~i;i=head[u])//这里就是优化的地方{head[u]=edge[i].p;//譬如起始点u点连接了10000个点 u->1>2>3>4>5>.........//那么我一下循环到u点的时候,它又要从1,2,3,4,5一个一个判断之前是否走过//而现在当我们从u走到过1这个位置后，head[u]=head[1]，那么u->1这条边就不在判断了//也就是说走过一条边这条边下次就不再走了，那么复杂度就是O(m)int v=edge[i].to;if(edge[i].vis)continue;edge[i].vis=1;if(i&1)edge[i+1].vis=1;elseedge[i-1].vis=1;dfs_unedge(v);ans[++cnt]=(i+1)/2;if(i%2==0)ans[cnt]*=-1;}
}
void dfs_diredge(int u)
{for(int i=head[u];~i;i=head[u]){head[u]=edge[i].p;int v=edge[i].to;if(edge[i].vis==0){edge[i].vis=1;dfs_diredge(v);ans[++cnt]=i;}}
}
int main()
{int t,x,y;scanf("%d%d%d",&t,&n,&m);init();for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y);if(t==1){add(y,x);in[x]++;in[y]++;}else{out[x]++;in[y]++;}}if(t==1)//条件1.1{for(int i=1;i<=n;i++)if(in[i]&1)return !printf("NO\n");}else//条件1.2{for(int i=1;i<=n;i++)if(in[i]!=out[i])return !printf("NO\n");}if(t==1) dfs_unedge(x);//else dfs_diredge(x);if(cnt!=m)//条件2printf("NO\n");else{printf("YES\n");for(int i=cnt;i>=1;i--)printf("%d ",ans[i]);}return 0;
}
这篇关于uoj 117 欧拉回路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
