1380 一笔画问题
2023-12-14 01:09:53
如果一个无向图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。
#include<bits/stdc++.h>
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,reckon,oddity_point,lt;
void dfs(int i)
{
for(int j=1;j<=n;j++)
{
if(g[i][j]==1)
{
g[i][j]=0;
g[j][i]=0;
dfs(j);
}
}
c[++reckon]=i;
return;
}
int main()
{
cin>>n>>m;
int x,y;
memset(g,0,sizeof(g));
for(int i=1;i<=m;i++)
{
cin>>x>>y;
g[x][y]=1;
g[y][x]=1;
d[x]++;
d[y]++;
}
int z=1;
for(int i=1;i<=n;i++)
{
if(d[i]%2==1)
{
z=i;
oddity_point++;
}
if(d[i]==0)
{
lt++;
}
}
dfs(z);
if(oddity_point!=2&&oddity_point!=0)
{
cout<<"NO";
return 0;
}
if(lt!=0)
{
cout<<"NO";
return 0;
}
for(int i=1;i<=reckon;i++)
{
cout<<c[i]<<" ";
}
return 0;
}
文章来源:https://blog.csdn.net/2301_76204446/article/details/134816605
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!