继承上面我发的帖子，我发现好像真的没有高效求哈密顿路径的算法或者结论。

在此之前，我在学校自己YY出了一个算法，可以$O(m)$判断该图是否有哈密顿路径。其中，$m$为边数。

当然，我并不知道这个算法或复杂度是否正确，如有错误，欢迎hack/指正。

讲一下过程吧：

这里的图是无向图，有向图还尚未得知是否可行。

• 1、建图，找到所有点的入度。由于是无向边，所以入度就为与该点相连的边的条数

• 2、遍历所有点，找到入度最小的那个点，并以该点为起点

• 3、遍历与该点相连的所有边，切除这些边，并找到：与之相连的点中入度最小的那个点。

• 4、以3中找到的那个点作为新的起点，重复3步骤，直至无法访问下一个点为止。

• 5、若访问次数为n(结点总数)，则存在哈密顿路径。

因为每个边至多被切除$1$次，切除过后不会重复访问，所以复杂度为$O(m)$。

至于为什么要连入度最小得点，简单说明一下：

若有入度更大的点，说明有更多方案能连上这个点，所以我们先解决入度小的点。（毕竟每访问一个点就要切边，后访问入度小的点可能就访问不到了）

这个算法我自己构造了好几个图都是正确的。但尚不清楚大数据是否也是正确的。

这里再贴一下代码吧。

/*
1、建图，找到所有点的入度。由于是双向边，所以入度就为与该点相连的边的条数
2、遍历所有点，找到入度最小的那个点，并以该点为起点 
3、遍历与该点相连的所有边，切除这些边，并找到：与之相连的点中入度最小的那个点。 
4、以3中找到的那个点作为新的起点，重复3步骤，直至无法访问下一个点为止。 
5、若访问次数为n(结点总数)，则存在哈密顿路径。 
*/
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;

int n, m, cnt;
int head[maxn], rd[maxn];
bool used[maxn];

struct edge
{
	int nxt, to, tsk;//tsk为记录双向边另一条边的编号。 
}e[maxn];

void add_edge(int u, int v)
{
	e[++ cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

void hmt()
{
	int mrd = inf, mi, num = 0;
	for(int i = 1; i <= n; i ++) 
	 	if(mrd > rd[i]) mrd = rd[i], mi = i;
	int g = -1;
	while(g != 0)
	{
		num ++;
		g = 0;//计数器，看可不可以继续访问下一条边 
		mrd = inf;
		for(int i = head[mi]; i; i = e[i].nxt)
		{
			if(used[i]) continue;//已经被切去 
			used[i] = true;
			used[e[i].tsk] = true;//没被切就切掉双向边 
			int mj = e[i].to;
			if(mrd > rd[mj]) mrd = rd[mj], mi = mj;//找与之相连最小入度的边
			rd[mi] --;
			rd[mj] --;//由于边被切掉，所以入度也要减 
			g ++;//能访问到一条边 
		}
	}
	if(num == n) printf("Yes");//访问了所有点说明有这么一条路 
	else printf("No");
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		e[cnt].tsk = cnt + 1;
		add_edge(v, u);
		e[cnt].tsk = cnt - 1;
		rd[u] ++;
		rd[v] ++;//建图，没什么好说的	
	}
	hmt();
	return 0;
}

求DALAO进来看看吧QAQ