当当当~
又到了解疑的时候啦~
今天给小伙伴们讲一下
哈密尔顿环
首先我们来看一下题目
题目描述
哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。
第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
汉密尔顿环,输出一条路径即可。
55
12
23
34
45
51
解题思路
核心思路：图论+回溯深搜
-哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路；
-用二维数组模拟邻接矩阵存储图；
-每一个点都作为起点进行尝试，注意同一个环不需要重复输出；
-遍历所有相连的点，注意回溯；
下面是参考代码~
"#includebits/stdc++.h
usingnamespacestd;
intstart,length,x,n;
boolvisited[],v1[];
intans[],num[];
intg[][];
voidprint()
{
for(inti=1;i=length;i++)
coutans"";
coutendl;
}
voiddfs(intlast,inti)
{
visited=1;
v1=1;
length++;
ans[length]=i;
for(intj=1;j=num;j++)
{
if(g[j]==xg[j]!=last)
{
length++;
ans[length]=g[j];
print();
length--;
break;
}
if(visited[g[j]]==0)dfs(i,g[j]);
}
length--;
visited=0;
}
intmain()
{
cinn;
intm;
cinm;
for(inti=1;i=m;i++)
{
intx,y;
cinxy;
num[x]++;
num[y]++;
g[x][num[x]]=y;
g[y][num[y]]=x;
}
for(x=1;x=n;x++)
if(v1[x]==0)
{
length=0;
dfs(0,x);
}
}
"▼
点击了解更多详情
▼
成绩展示
喜报
CCFCSP-J/S第二轮认证评级，机房日子编程再创佳绩!
年NOI与NOIP获奖学员公示！新的一年我们再次出发！
机房课程
课程
线上一对一课程，为你量身定制!
搜索基础课程与动态规划基础课程
算法与数据结构专题课
NOIP数学专题课
《动态规划》特设专题课
机房解疑
机房解疑
不等数列
机房解疑
记数问题
机房解疑
进制转换
机房解疑
四方定理
机房解疑
最大正方形
机房解疑
欧拉路
机房解疑
一元三次方程求解
机房解疑
装箱问题
机房解疑
均分纸牌
机房解疑
排队接水
机房解疑
货币系统
机房解疑
喝醉的狱卒
机房解疑
完全背包
机房解疑
01背包
机房解疑
合并石子（直线问题）
机房解疑
黑白棋子的移动
机房解疑
N皇后
机房解疑
逆序对
机房解疑
归并排序
机房解疑
快速排序
机房解疑
约瑟夫问题-猴子选大王
机房解疑
递归-汉诺塔问题
机房解疑
搜索-全排列
机房解疑
高精度运算，不简单的A+B
机房分享
机房分享
信息学奥赛的10大误区
机房分享
送给NOIP竞赛学生的几条建议！
机房分享
五大学科竞赛到底能给我们带来什么？
机房分享
信息学奥赛（NOIP）复赛学习方法与备考攻略
机房分享
新手入门信息学奥赛（NOIP）常见问题解答
机房分享
NOIP复赛知识点简述及复赛算法总结
机房分享
计算机基本常识与初赛真题选讲
扫描下方