网站的url是什么/福州网站排名推广

概念

“哈密尔顿回路问题”是访问除原出发结点以外的每个结点一次且仅一次，而“欧拉回路问题”是访问每条边一次且仅一次

欧拉回路与欧拉路

PS：已经判断此图有欧拉路或欧拉回路

#include<iostream>
using namespace std;
int g[101][101];
int du[101];
int lu[101];
int n,e,l,start,x,y;
int maxn,minn=99999;
int find(int i)
{for(int j=1;j<=n;j++){if(g[i][j]==1){g[i][j]=0;//删除边 避免走第二次g[j][i]=0;//如果有重边改为--find(j);}}lu[++l]=i;//记录路径
}
int main()
{cin>>n>>e;for(int i=1;i<=e;i++){cin>>x>>y;g[x][y]=1;//如果有重边改为＋＋g[y][x]=1;du[x]++;du[y]++;maxn=max(maxn,max(x,y));//点编号的最大值minn=min(minn,min(x,y));//点编号的最小值}start=1;for(int i=1;i<=n;i++)if(du[i]%2==1)//判断如果有奇点从奇点开始start=i;find(start);for(int i=l;i>=1;i--)cout<<lu[i];
}

哈密尔顿环

#include<iostream>
#include<cstring>
using namespace std;
bool flag[101];
bool v[101];
int n,e,start,x,l;
int a[101][101];
int lu[101];
int num[101];
void print()
{for(int i=1;i<=l;i++)cout<<lu[i]<<" ";cout<<endl;
}
void dfs(int last,int i)
{flag[i]=1;//标记走过v[i]=1;//出现在图中lu[++l]=i;//记录路径for(int j=1;j<=num[i];j++){if(a[i][j]==x&&a[i][j]!=last)//它可以回到头且不是第二个点就是一个环{lu[++l]=a[i][j];print();l--;break;}if(flag[a[i][j]]==0)dfs(i,a[i][j]);}l--;//回溯部分v[i]=0;
}
int main()
{cin>>n>>e;for(int i=1;i<=e;i++){int x,y;cin>>x>>y;a[x][++num[x]]=y;//每个点可以到达几个点a[y][++num[y]]=x;}for(x=1;x<=n;x++){if(v[x]==0)//如果没有出现在图中{l=0;dfs(0,x);}}
}