哈密顿回路算法
概念：
哈密顿图：图g的一个回路，若它通过图的每一个节点一次，且仅一次，就是哈密顿回路。存在哈密顿回路的图就是哈密顿图。哈密顿图就是从一点出发，经过所有的必须且只能一次，最终回到起点的路径。图中有的边可以不经过，但是不会有边被经过两次。
与欧拉图的区别：欧拉图讨论的实际上是图上关于边的可行便利问题，而哈密顿图的要求与点有关。
判定： 一：dirac定理（充分条件）
设一个无向图中有n个顶点，若所有顶点的度数大于等于n/2，则哈密顿回路一定存在。（n/2指的是⌈n/2⌉，向上取整）
二：基本的必要条件
设图g=《v， e》是哈密顿图，则对于v的任意一个非空子集s，若以|s|表示s中元素的数目，g-s表示g中删除了s中的点以及这些点所关联的边后得到的子图，则w（g-s）《=|s|成立。其中w（g-s）是g-s中联通分支数。
三：竞赛图（哈密顿通路）
n（n》=2）阶竞赛图一点存在哈密顿通路。
算法： 一：在dirac定理的前提下构造哈密顿回路 过程：
1：任意找两个相邻的节点s和t，在其基础上扩展出一条尽量长的没有重复结点的路径。即如果s与结点v相邻，而且v不在路径s -》 t上，则可以把该路径变成v -》 s -》 t，然后v成为新的s.从s和t分别向两头扩展，直到无法继续扩展为止，即所有与s或t相邻的节点都在路径s -》 t上。
2：若s与t相邻，则路径s -》 t形成了一个回路。
3：若s与t不相邻，可以构造出来一个回路。设路径s -》 t上有k+2个节点，依次为s， v1， v2， 。。。， vk， t.可以证明存在节点vi（i属于［1， k］），满足vi与t相邻，且vi+1与s相邻。找到这个节点vi，把原路径变成s -》 vi -》 t -》 vi+1 -》 s，即形成了一个回路。
4：到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为n，则哈密顿回路就找到了。如果回路的长度小于n，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径，则一定有新的节点被加进来。接着回到路径2.
证明：
可利用鸽巢原理证明。
伪代码：
设s为哈密顿回路的起始点，t为哈密顿回路中终点s之前的点.ans［］为最终的哈密顿回路。倒置的意思指的是将数组对应的区间中数字的排列顺序方向。
1：初始化，令s = 1，t为s的任意一个邻接点。
2：如果ans［］中元素的个数小于n，则从t开始向外扩展，如果有可扩展点v，放入ans［］的尾部，并且t=v，并继续扩展，如无法扩展进入步骤3.
3：将当前得到的ans［］倒置，s和t互换，从t开始向外扩展，如果有可扩展点v，放入ans［］尾部，并且t=v，并继续扩展。如无法扩展进入步骤4.
4：如果当前s和t相邻，进入步骤5.否则，遍历ans［］，寻找点ans［i］，使得ans［i］与t相连并且ans［i +１］与ｓ相连，将从ans［i + 1］到t部分的ans［］倒置，t=ans［i +１］，进如步骤5.
5：如果当前ans［］中元素的个数等于n，算法结束，ans［］中保存了哈密顿回路（可看情况是否加入点s）。否则，如果s与t连通，但是ans［］中的元素的个数小于n，则遍历ans［］，寻找点ans［i］，使得ans［i］与ans［］外的一点（j）相连，则令s=ans［i - 1］，t = j，将ans［］中s到ans［i - 1］部分的ans［］倒置，将ans［］中的ans［i］到t的部分倒置，将点j加入到ans［］的尾部，转步骤2.
时间复杂度：
如果说每次到步骤5算一轮的话，那么由于每一轮当中至少有一个节点被加入到路径s -》 t中，所以总的轮数肯定不超过n轮，所以时间复杂度为o（n^2）。空间上由于边数非常多，所以采用邻接矩阵来存储比较适合。
代码：
const int maxn = 100;
inline void reverse（int arv［maxn + 7］， int s， int t）{//将数组anv从下标s到t的部分的顺序反向
int temp;
while（s 《 t）{
temp = arv［s］;
arv［s］ = arv［t］;
arv［t］ = temp;
s++;
t--;
}
}
void hamilton（int ans［maxn + 7］， bool map［maxn + 7］［maxn + 7］， int n）{
int s = 1， t;//初始化取s为1号点
int ansi = 2;
int i， j;
int w;
int temp;
bool visit［maxn + 7］ = {false};
for（i = 1; i 《= n; i++） if（map［s］［i］） break;
t = i;//取任意邻接与s的点为t
visit［s］ = visit［t］ = true;
ans［0］ = s;
ans［1］ = t;
while（true）{
while（true）{//从t向外扩展
for（i = 1; i 《= n; i++）{
if（map［t］［i］ && ！visit［i］）{
ans［ansi++］ = i;
visit［i］ = true;
t = i;
break;
}
}
if（i 》 n） break;
}
w = ansi - 1;//将当前得到的序列倒置，s和t互换，从t继续扩展，相当于在原来的序列上从s向外扩展
i = 0;
reverse（ans， i， w）;
temp = s;
s = t;
t = temp;
while（true）{//从新的t继续向外扩展，相当于在原来的序列上从s向外扩展
for（i = 1; i 《= n; i++）{
if（map［t］［i］ && ！visit［i］）{
ans［ansi++］ = i;
visit［i］ = true;
t = i;
break;
}
}
if（i 》 n） break;
}
if（！map［s］［t］）{//如果s和t不相邻，进行调整
for（i = 1; i 《 ansi - 2; i++）//取序列中的一点i，使得ans［i］与t相连，并且ans［i+1］与s相连
if（map［ans［i］］［t］ && map［s］［ans［i + 1］］）break;
w = ansi - 1;
i++;
t = ans［i］;
reverse（ans， i， w）;//将从ans［i +１］到ｔ部分的ans［］倒置
}//此时s和t相连
if（ansi == n） return;//如果当前序列包含n个元素，算法结束
for（j = 1; j 《= n; j++）{//当前序列中元素的个数小于n，寻找点ans［i］，使得ans［i］与ans［］外的一个点相连
if（visit［j］） continue;
for（i = 1; i 《 ansi - 2; i++）if（map［ans［i］］［j］）break;
if（map［ans［i］］［j］） break;
}
s = ans［i - 1］;
t = j;//将新找到的点j赋给t
reverse（ans， 0， i - 1）;//将ans［］中s到ans［i-1］的部分倒置
reverse（ans， i， ansi - 1）;//将ans［］中ans［i］到t的部分倒置
ans［ansi++］ = j;//将点j加入到ans［］尾部
visit［j］ = true;
}
}
二：n（n》=2）阶竞赛图构造哈密顿通路 n阶竞赛图：含有n个顶点的有向图，且每对顶点之间都有一条边。对于n阶竞赛图一定存在哈密顿通路。
数学归纳法证明竞赛图在n 》= 2时必存在哈密顿路：
（1）n = 2时结论显然成立；
（2）假设n = k时，结论也成立，哈密顿路为v1， v2， v3， 。。。， vk;
设当n = k+1时，第k + 1个节点为v（k+1），考虑到v（k+1）与vi（1《=i《=k）的连通情况，可以分为以下两种情况。
1:vk与v（k+1）两点之间的弧为《vk， v（k+1）》，则可构造哈密顿路径v1， v2，…， vk， v（k+1）。
2:vk与v（k+1）两点之间的弧为《v（k+1），vk》，则从后往前寻找第一个出现的vi（i=k-1，i》=1，--i），满足vi与v（k+1）之间的弧为《vi，v（k+1）》，则构造哈密顿路径v1， v2， …， vi， v（k+1）， v（i+1）， …， v（k）。若没找到满足条件的vi，则说明对于所有的vi（1《=i《=k）到v（k+1）的弧为《v（k+1），v（i）》，则构造哈密顿路径v（k+1）， v1， v2， …， vk.证毕。
竞赛图构造哈密顿路时的算法同以上证明过程。
用图来说明：
假设此时已经存在路径v1 -》 v2 -》 v3 -》 v4，这四个点与v5的连通情况有16种，给定由0/1组成的四个数，第i个数为0代表存在弧《v5，vi》，反之为1，表示存在弧《vi，v5》
sign［］={0， 0， 0， 0}。
很显然属于第二种情况，从后往前寻找不到1，即且不存在弧《vi， v5》。
则构造哈密顿路：v5 -》 v1 -》 v2 -》 v3 -》 v4.
sign［］={0， 0， 0， 1}。
属于第一种情况，最后一个数字为1，即代表存在弧《vi， v5》且i=4（最后一个点）
则构造哈密顿路： v1 -》 v2 -》 v3 -》 v4 -》 v5.
sign［］={0， 0， 1， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为3.
构造哈密顿路： v1 -》 v2 -》 v3 -》 v5 -》 v4.
sign［］={0， 0， 1， 1}。
属于第一种情况，最后一个数字为1，即代表存在弧《vi， v5》且i=4（最后一个点）
则构造哈密顿路： v1 -》 v2 -》 v3 -》 v4 -》 v5.
sign［］={0， 1， 0， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为2.
构造哈密顿路： v1 -》 v2 -》 v5 -》 v3-》 v4.
sign［］={0， 1， 0， 1}。
属于第一种情况，最后一个数字为1，即代表存在弧《vi， v5》且i=4（最后一个点）
则构造哈密顿路：v1 -》 v2 -》 v3 -》 v4 -》 v5.（就不举末尾为1的栗子了~~）
sign［］={1， 0， 1， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为3.
构造哈密顿路： v1 -》 v2 -》 v3 -》 v5-》 v4.
sign［］={1， 1， 1， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为3.
构造哈密顿路： v1 -》 v2 -》 v3 -》 v5-》 v4.
sign［］={1， 1， 1， 1}。
同样最后一位为1，代表存在《vi， v5》且i=4（最后一位）
则构造哈密顿路：v1 -》 v2 -》 v3 -》 v4 -》 v5.以上是当n=4时（n+1=5），用图来阐述算法的过程。
注意从后往前找不是找这个点编号之前的点，即不是按照编号来的，而是按照当前哈密顿序列从后往前找的。举个栗子：
4
2 1
1 3
3 2
4 1
4 2
4 3
第一步ans={1}
第二步ans={2，1}
第三步sign={0， 1}（map［3］［2］ = 0，map［3］［1］ = 1，当前序列为2，1） ，而不是{1， 0}（1，2），因为存在弧《v1， v3》和《v3， v2》。这里需要注意下。
代码：
#include 《iostream》
#include 《cmath》
#include 《cstdio》
#include 《cstring》
#include 《cstdlib》
#include 《algorithm》
#include 《queue》
#include 《stack》
#include 《vector》
using namespace std;
typedef long long ll;
const int maxn = 200;
//the arv［］ length is len， insert key befor arv［index］
inline void insert（int arv［］， int &len， int index， int key）{
if（index 》 len） index = len;
len++;
for（int i = len - 1; i 》= 0; --i）{
if（i ！= index && i）arv［i］ = arv［i - 1］;
else{arv［i］ = key; return;}
}
}
void hamilton（int ans［maxn + 7］， int map［maxn + 7］［maxn + 7］， int n）{
int ansi = 1;
ans［ansi++］ = 1;
for（int i = 2; i 《= n; i++）{//第一种情况，直接把当前点添加到序列末尾
if（map［i］［ans［ansi - 1］］ == 1）
ans［ansi++］ = i;
else{
int flag = 0;
for（int j = ansi - 2; j 》 0; --j）{//在当前序列中，从后往前找到第一个满足条件的点j，使得存在《vj，vi》且《vi， vj+1》。
if（map［i］［ans［j］］ == 1）{//找到后把该点插入到序列的第j + 1个点前。
flag = 1;
insert（ans， ansi， j + 1， i）;
break;
}
}
if（！flag）insert（ans， ansi， 1， i）;//否则说明所有点都邻接自点i，则把该点直接插入到序列首端。
}
}
}
int main（）
{
//freopen（“input.txt”， “r”， stdin）;
int t;
scanf（“%d”， &t）;
while（t--）{
int n;
scanf（“%d”， &n）;
int m = n * （n - 1） / 2;
int map［maxn + 7］［maxn + 7］ = {0};
for（int i = 0; i 《 m; i++）{
int u， v;
scanf（“%d%d”， &u， &v）;
//map［i］［j］为1说明j 《 i，且存在弧《vi， vj》，因为插入时只考虑该点之前的所有点的位置，与之后的点没有关系。所以只注重该点与其之前的点的连通情况。
if（u 《 v）map［v］［u］ = 1;
}
int ans［maxn + 7］ = {0};
hamilton（ans， map， n）;
for（int i = 1; i 《= n; i++）
printf（i == 1 ？ “%d”：“ %d”， ans［i］）;
printf（“”）;
}
return 0;
}
代码2:void hamilton（int ans［maxn + 7］， int map［maxn + 7］［maxn + 7］， int n）{
int nxt［maxn + 7］;
memset（nxt， -1， sizeof（nxt））;
int head = 1;
for（int i = 2; i 《= n; i++）{
if（map［i］［head］）{
nxt［i］ = head;
head = i;
}else{
int pre = head， pos = nxt［head］;
while（pos ！= -1 && ！map［i］［pos］）{
pre = pos;
pos = nxt［pre］;
}
nxt［pre］ = i;
nxt［i］ = pos;
}
}
int cnt = 0;
for（int i = head; i ！= -1; i = nxt［i］）
ans［++cnt］ = i;
}
代码三：
void hamitton（bool reach［n + 7］［n + 7］， int n）
{
vector 《int》 ans;
ans.push_back（1）;
for（int i=2;i 《= n;i++）
{
bool cont = false;
for（int j=0;j《（int）ans.size（）-1;j++）
if（reach［ ans［j］ ］［i］ && reach［i］［ ans［j+1］ ］）
{
ans.insert（ans.begin（）+j+1，i）;
cont = true;
break;
}
if（cont）
continue;
if（reach［ ans.back（） ］［i］）
ans.push_back（i）;
else
ans.insert（ans.begin（），i）;
}
for（int i=0;i《n;i++）
printf（“%d%c”，ans［i］，i==n-1？‘’：‘ ’）;
}
时代民芯宣布在上海浦东成立控股公司-宇芯科技
这几个电阻在制作三极管电路中的作用
移远通信与爱立信联手共同探索行业5G应用的落地
爱奇艺VR一体机奇遇2S评测 已经彻底跨越了尝鲜的价值
有源钳位反激(ACF)变换器控制方案(1)
哈密顿回路算法
大数据挖掘，数据结构化首当其冲
在平面国生活，会是怎样的体验？
什么是AC97
带CPU芯片电路板的维修方法
高合汽车否认暂停所有业务
活跃用户数超3亿 我国已真正使用IPv6地址
基于MPY634的有效值电路设计
一个嵌入式通用软件包：ToolKit
Python是一种什么语言，它可以用来做些什么
摩擦带电电荷密度测定仪的特征是什么
Gospelwin Type-C5A数据线相当给力的功能性能
电力变压器型号的含义
智能手表、手环大厂2016过的怎么样？
Vivo计划到明年年底加大印度本地智能手机部件采购比例
与欧拉图的区别：欧拉图讨论的实际上是图上关于边的可行便利问题，而哈密顿图的要求与点有关。
判定： 一：dirac定理（充分条件）
设一个无向图中有n个顶点，若所有顶点的度数大于等于n/2，则哈密顿回路一定存在。（n/2指的是⌈n/2⌉，向上取整）
二：基本的必要条件
设图g=《v， e》是哈密顿图，则对于v的任意一个非空子集s，若以|s|表示s中元素的数目，g-s表示g中删除了s中的点以及这些点所关联的边后得到的子图，则w（g-s）《=|s|成立。其中w（g-s）是g-s中联通分支数。
三：竞赛图（哈密顿通路）
n（n》=2）阶竞赛图一点存在哈密顿通路。
算法： 一：在dirac定理的前提下构造哈密顿回路 过程：
1：任意找两个相邻的节点s和t，在其基础上扩展出一条尽量长的没有重复结点的路径。即如果s与结点v相邻，而且v不在路径s -》 t上，则可以把该路径变成v -》 s -》 t，然后v成为新的s.从s和t分别向两头扩展，直到无法继续扩展为止，即所有与s或t相邻的节点都在路径s -》 t上。
2：若s与t相邻，则路径s -》 t形成了一个回路。
3：若s与t不相邻，可以构造出来一个回路。设路径s -》 t上有k+2个节点，依次为s， v1， v2， 。。。， vk， t.可以证明存在节点vi（i属于［1， k］），满足vi与t相邻，且vi+1与s相邻。找到这个节点vi，把原路径变成s -》 vi -》 t -》 vi+1 -》 s，即形成了一个回路。
4：到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为n，则哈密顿回路就找到了。如果回路的长度小于n，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径，则一定有新的节点被加进来。接着回到路径2.
证明：
可利用鸽巢原理证明。
伪代码：
设s为哈密顿回路的起始点，t为哈密顿回路中终点s之前的点.ans［］为最终的哈密顿回路。倒置的意思指的是将数组对应的区间中数字的排列顺序方向。
1：初始化，令s = 1，t为s的任意一个邻接点。
2：如果ans［］中元素的个数小于n，则从t开始向外扩展，如果有可扩展点v，放入ans［］的尾部，并且t=v，并继续扩展，如无法扩展进入步骤3.
3：将当前得到的ans［］倒置，s和t互换，从t开始向外扩展，如果有可扩展点v，放入ans［］尾部，并且t=v，并继续扩展。如无法扩展进入步骤4.
4：如果当前s和t相邻，进入步骤5.否则，遍历ans［］，寻找点ans［i］，使得ans［i］与t相连并且ans［i +１］与ｓ相连，将从ans［i + 1］到t部分的ans［］倒置，t=ans［i +１］，进如步骤5.
5：如果当前ans［］中元素的个数等于n，算法结束，ans［］中保存了哈密顿回路（可看情况是否加入点s）。否则，如果s与t连通，但是ans［］中的元素的个数小于n，则遍历ans［］，寻找点ans［i］，使得ans［i］与ans［］外的一点（j）相连，则令s=ans［i - 1］，t = j，将ans［］中s到ans［i - 1］部分的ans［］倒置，将ans［］中的ans［i］到t的部分倒置，将点j加入到ans［］的尾部，转步骤2.
时间复杂度：
如果说每次到步骤5算一轮的话，那么由于每一轮当中至少有一个节点被加入到路径s -》 t中，所以总的轮数肯定不超过n轮，所以时间复杂度为o（n^2）。空间上由于边数非常多，所以采用邻接矩阵来存储比较适合。
代码：
const int maxn = 100;
inline void reverse（int arv［maxn + 7］， int s， int t）{//将数组anv从下标s到t的部分的顺序反向
int temp;
while（s 《 t）{
temp = arv［s］;
arv［s］ = arv［t］;
arv［t］ = temp;
s++;
t--;
}
}
void hamilton（int ans［maxn + 7］， bool map［maxn + 7］［maxn + 7］， int n）{
int s = 1， t;//初始化取s为1号点
int ansi = 2;
int i， j;
int w;
int temp;
bool visit［maxn + 7］ = {false};
for（i = 1; i 《= n; i++） if（map［s］［i］） break;
t = i;//取任意邻接与s的点为t
visit［s］ = visit［t］ = true;
ans［0］ = s;
ans［1］ = t;
while（true）{
while（true）{//从t向外扩展
for（i = 1; i 《= n; i++）{
if（map［t］［i］ && ！visit［i］）{
ans［ansi++］ = i;
visit［i］ = true;
t = i;
break;
}
}
if（i 》 n） break;
}
w = ansi - 1;//将当前得到的序列倒置，s和t互换，从t继续扩展，相当于在原来的序列上从s向外扩展
i = 0;
reverse（ans， i， w）;
temp = s;
s = t;
t = temp;
while（true）{//从新的t继续向外扩展，相当于在原来的序列上从s向外扩展
for（i = 1; i 《= n; i++）{
if（map［t］［i］ && ！visit［i］）{
ans［ansi++］ = i;
visit［i］ = true;
t = i;
break;
}
}
if（i 》 n） break;
}
if（！map［s］［t］）{//如果s和t不相邻，进行调整
for（i = 1; i 《 ansi - 2; i++）//取序列中的一点i，使得ans［i］与t相连，并且ans［i+1］与s相连
if（map［ans［i］］［t］ && map［s］［ans［i + 1］］）break;
w = ansi - 1;
i++;
t = ans［i］;
reverse（ans， i， w）;//将从ans［i +１］到ｔ部分的ans［］倒置
}//此时s和t相连
if（ansi == n） return;//如果当前序列包含n个元素，算法结束
for（j = 1; j 《= n; j++）{//当前序列中元素的个数小于n，寻找点ans［i］，使得ans［i］与ans［］外的一个点相连
if（visit［j］） continue;
for（i = 1; i 《 ansi - 2; i++）if（map［ans［i］］［j］）break;
if（map［ans［i］］［j］） break;
}
s = ans［i - 1］;
t = j;//将新找到的点j赋给t
reverse（ans， 0， i - 1）;//将ans［］中s到ans［i-1］的部分倒置
reverse（ans， i， ansi - 1）;//将ans［］中ans［i］到t的部分倒置
ans［ansi++］ = j;//将点j加入到ans［］尾部
visit［j］ = true;
}
}
二：n（n》=2）阶竞赛图构造哈密顿通路 n阶竞赛图：含有n个顶点的有向图，且每对顶点之间都有一条边。对于n阶竞赛图一定存在哈密顿通路。
数学归纳法证明竞赛图在n 》= 2时必存在哈密顿路：
（1）n = 2时结论显然成立；
（2）假设n = k时，结论也成立，哈密顿路为v1， v2， v3， 。。。， vk;
设当n = k+1时，第k + 1个节点为v（k+1），考虑到v（k+1）与vi（1《=i《=k）的连通情况，可以分为以下两种情况。
1:vk与v（k+1）两点之间的弧为《vk， v（k+1）》，则可构造哈密顿路径v1， v2，…， vk， v（k+1）。
2:vk与v（k+1）两点之间的弧为《v（k+1），vk》，则从后往前寻找第一个出现的vi（i=k-1，i》=1，--i），满足vi与v（k+1）之间的弧为《vi，v（k+1）》，则构造哈密顿路径v1， v2， …， vi， v（k+1）， v（i+1）， …， v（k）。若没找到满足条件的vi，则说明对于所有的vi（1《=i《=k）到v（k+1）的弧为《v（k+1），v（i）》，则构造哈密顿路径v（k+1）， v1， v2， …， vk.证毕。
竞赛图构造哈密顿路时的算法同以上证明过程。
用图来说明：
假设此时已经存在路径v1 -》 v2 -》 v3 -》 v4，这四个点与v5的连通情况有16种，给定由0/1组成的四个数，第i个数为0代表存在弧《v5，vi》，反之为1，表示存在弧《vi，v5》
sign［］={0， 0， 0， 0}。
很显然属于第二种情况，从后往前寻找不到1，即且不存在弧《vi， v5》。
则构造哈密顿路：v5 -》 v1 -》 v2 -》 v3 -》 v4.
sign［］={0， 0， 0， 1}。
属于第一种情况，最后一个数字为1，即代表存在弧《vi， v5》且i=4（最后一个点）
则构造哈密顿路： v1 -》 v2 -》 v3 -》 v4 -》 v5.
sign［］={0， 0， 1， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为3.
构造哈密顿路： v1 -》 v2 -》 v3 -》 v5 -》 v4.
sign［］={0， 0， 1， 1}。
属于第一种情况，最后一个数字为1，即代表存在弧《vi， v5》且i=4（最后一个点）
则构造哈密顿路： v1 -》 v2 -》 v3 -》 v4 -》 v5.
sign［］={0， 1， 0， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为2.
构造哈密顿路： v1 -》 v2 -》 v5 -》 v3-》 v4.
sign［］={0， 1， 0， 1}。
属于第一种情况，最后一个数字为1，即代表存在弧《vi， v5》且i=4（最后一个点）
则构造哈密顿路：v1 -》 v2 -》 v3 -》 v4 -》 v5.（就不举末尾为1的栗子了~~）
sign［］={1， 0， 1， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为3.
构造哈密顿路： v1 -》 v2 -》 v3 -》 v5-》 v4.
sign［］={1， 1， 1， 0}。
属于第二种情况，从后往前找到1出现的第一个位置为3.
构造哈密顿路： v1 -》 v2 -》 v3 -》 v5-》 v4.
sign［］={1， 1， 1， 1}。
同样最后一位为1，代表存在《vi， v5》且i=4（最后一位）
则构造哈密顿路：v1 -》 v2 -》 v3 -》 v4 -》 v5.以上是当n=4时（n+1=5），用图来阐述算法的过程。
注意从后往前找不是找这个点编号之前的点，即不是按照编号来的，而是按照当前哈密顿序列从后往前找的。举个栗子：
4
2 1
1 3
3 2
4 1
4 2
4 3
第一步ans={1}
第二步ans={2，1}
第三步sign={0， 1}（map［3］［2］ = 0，map［3］［1］ = 1，当前序列为2，1） ，而不是{1， 0}（1，2），因为存在弧《v1， v3》和《v3， v2》。这里需要注意下。
代码：
#include 《iostream》
#include 《cmath》
#include 《cstdio》
#include 《cstring》
#include 《cstdlib》
#include 《algorithm》
#include 《queue》
#include 《stack》
#include 《vector》
using namespace std;
typedef long long ll;
const int maxn = 200;
//the arv［］ length is len， insert key befor arv［index］
inline void insert（int arv［］， int &len， int index， int key）{
if（index 》 len） index = len;
len++;
for（int i = len - 1; i 》= 0; --i）{
if（i ！= index && i）arv［i］ = arv［i - 1］;
else{arv［i］ = key; return;}
}
}
void hamilton（int ans［maxn + 7］， int map［maxn + 7］［maxn + 7］， int n）{
int ansi = 1;
ans［ansi++］ = 1;
for（int i = 2; i 《= n; i++）{//第一种情况，直接把当前点添加到序列末尾
if（map［i］［ans［ansi - 1］］ == 1）
ans［ansi++］ = i;
else{
int flag = 0;
for（int j = ansi - 2; j 》 0; --j）{//在当前序列中，从后往前找到第一个满足条件的点j，使得存在《vj，vi》且《vi， vj+1》。
if（map［i］［ans［j］］ == 1）{//找到后把该点插入到序列的第j + 1个点前。
flag = 1;
insert（ans， ansi， j + 1， i）;
break;
}
}
if（！flag）insert（ans， ansi， 1， i）;//否则说明所有点都邻接自点i，则把该点直接插入到序列首端。
}
}
}
int main（）
{
//freopen（“input.txt”， “r”， stdin）;
int t;
scanf（“%d”， &t）;
while（t--）{
int n;
scanf（“%d”， &n）;
int m = n * （n - 1） / 2;
int map［maxn + 7］［maxn + 7］ = {0};
for（int i = 0; i 《 m; i++）{
int u， v;
scanf（“%d%d”， &u， &v）;
//map［i］［j］为1说明j 《 i，且存在弧《vi， vj》，因为插入时只考虑该点之前的所有点的位置，与之后的点没有关系。所以只注重该点与其之前的点的连通情况。
if（u 《 v）map［v］［u］ = 1;
}
int ans［maxn + 7］ = {0};
hamilton（ans， map， n）;
for（int i = 1; i 《= n; i++）
printf（i == 1 ？ “%d”：“ %d”， ans［i］）;
printf（“”）;
}
return 0;
}
代码2:void hamilton（int ans［maxn + 7］， int map［maxn + 7］［maxn + 7］， int n）{
int nxt［maxn + 7］;
memset（nxt， -1， sizeof（nxt））;
int head = 1;
for（int i = 2; i 《= n; i++）{
if（map［i］［head］）{
nxt［i］ = head;
head = i;
}else{
int pre = head， pos = nxt［head］;
while（pos ！= -1 && ！map［i］［pos］）{
pre = pos;
pos = nxt［pre］;
}
nxt［pre］ = i;
nxt［i］ = pos;
}
}
int cnt = 0;
for（int i = head; i ！= -1; i = nxt［i］）
ans［++cnt］ = i;
}
代码三：
void hamitton（bool reach［n + 7］［n + 7］， int n）
{
vector 《int》 ans;
ans.push_back（1）;
for（int i=2;i 《= n;i++）
{
bool cont = false;
for（int j=0;j《（int）ans.size（）-1;j++）
if（reach［ ans［j］ ］［i］ && reach［i］［ ans［j+1］ ］）
{
ans.insert（ans.begin（）+j+1，i）;
cont = true;
break;
}
if（cont）
continue;
if（reach［ ans.back（） ］［i］）
ans.push_back（i）;
else
ans.insert（ans.begin（），i）;
}
for（int i=0;i《n;i++）
printf（“%d%c”，ans［i］，i==n-1？‘’：‘ ’）;
}
时代民芯宣布在上海浦东成立控股公司-宇芯科技
这几个电阻在制作三极管电路中的作用
移远通信与爱立信联手共同探索行业5G应用的落地
爱奇艺VR一体机奇遇2S评测 已经彻底跨越了尝鲜的价值
有源钳位反激(ACF)变换器控制方案(1)
哈密顿回路算法
大数据挖掘，数据结构化首当其冲
在平面国生活，会是怎样的体验？
什么是AC97
带CPU芯片电路板的维修方法
高合汽车否认暂停所有业务
活跃用户数超3亿 我国已真正使用IPv6地址
基于MPY634的有效值电路设计
一个嵌入式通用软件包：ToolKit
Python是一种什么语言，它可以用来做些什么
摩擦带电电荷密度测定仪的特征是什么
Gospelwin Type-C5A数据线相当给力的功能性能
电力变压器型号的含义
智能手表、手环大厂2016过的怎么样？
Vivo计划到明年年底加大印度本地智能手机部件采购比例