大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
n积分m文章无向边
它输出一个哈密顿电路
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 155;
int n, m;
bool mp[N][N];
int S, T, top, Stack[N];
bool vis[N];
void _reverse(int l,int r) {
while (l<r)
swap(Stack[l++],Stack[r--]);
}
void expand() {
while(1) {
bool flag = 0;
for (int i=1; i<=n && false == flag; i++)
if (!vis[i] && mp[T][i])
{
Stack[top++]=i;
T=i;
flag = vis[i] = 1;
}
if (!flag) return;
}
}
void hamiltun(int Start){
memset(vis, 0, sizeof vis);
S = Start;
for(T=2; T<=n; T++) //随意找两个相邻的节点S和T
if (mp[S][T]) break;
top = 0;
Stack[top++]=S;
Stack[top++]=T;
vis[S] = vis[T] = true;
while (1)
{
expand(); //在它们基础上扩展出一条尽量长的没有反复节点的路径:步骤1
_reverse(0,top-1);
swap(S,T);
expand(); //在它们基础上扩展出一条尽量长的没有反复节点的路径
int mid=0;
if (!mp[S][T]) //若S与T不相邻,能够构造出一个回路使新的S和T相邻
{
//设路径S→T上有k+2个节点,依次为S,v1,v2…… vk和T.
//能够证明存在节点vi,i∈[1,k),满足vi与T相邻,且vi+1与S相邻
for (int i=1; i<top-2; i++)
if (mp[Stack[i]][T] && mp[Stack[i+1]][S])
{
mid=i+1; break;
}
//把原路径变成S→vi→T→vi+1→S,即形成了一个回路
_reverse(mid,top-1);
T=Stack[top-1];
}
if (top==n) break;
//如今我们有了一个没有反复节点的回路.假设它的长度为N,则汉密尔顿回路就找到了
//否则,因为整个图是连通的,所以在该回路上,一定存在一点与回路以外的点相邻
//那么从该点处把回路断开,就变回了一条路径,再依照步骤1的方法尽量扩展路径
for (int i = 1, j; i <= n; i++)
if (!vis[i])
{
for (j=1; j<top-1; j++)
if (mp[Stack[j]][i]) break;
if (mp[Stack[j]][i])
{
T=i; mid=j;
break;
}
}
S=Stack[mid-1];
_reverse(0,mid-1);
_reverse(mid,top-1);
Stack[top++]=T;
vis[T]=true;
}
}
int main() {
while (cin>>n>>m) {
memset(mp, 0, sizeof mp);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d %d",&u, &v);
mp[u][v] = mp[v][u] = 1;
}
hamiltun(1);
for (int i = 0; i < top; i++)
printf("%d%c", Stack[i], i==top-1?'\n':' ');
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116761.html原文链接：https://javaforall.net
