HDU 4337 King Arthur＆＃39; S Knights it outputs a Hamiltonian circuit

Hello everyone , I meet you again , I'm the king of the whole stack

n integral m The article has no direction

It outputs a Hamiltonian circuit

#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++) // Randomly find two adjacent nodes S and T
		if (mp[S][T]) break; 
	top = 0;
	Stack[top++]=S;
	Stack[top++]=T;
	vis[S] = vis[T] = true;
	while (1)
	{
		expand(); // On the basis of them, expand a path without repeated nodes as long as possible : step 1
		_reverse(0,top-1);
		swap(S,T);
		expand(); // On the basis of them, expand a path without repeated nodes as long as possible 
		int mid=0;
		if (!mp[S][T]) // if S And T Not adjacent , Can construct a circuit to make a new S and T adjacent 
		{
			// Set path S→T There are k+2 Nodes , In turn S,v1,v2…… vk and T.
			// It can prove the existence of nodes vi,i∈[1,k), Satisfy vi And T adjacent , And vi+1 And S adjacent 
			for (int i=1; i<top-2; i++)
				if (mp[Stack[i]][T] && mp[Stack[i+1]][S])
				{
					mid=i+1; break;
				}
			// Turn the original path into S→vi→T→vi+1→S, It forms a loop 
			_reverse(mid,top-1);
			T=Stack[top-1];
		}
		if (top==n) break;
		// Now we have a loop without repeating nodes . Suppose its length is N, Then Hamilton loop is found 
		// otherwise , Because the whole graph is connected , So in this loop , There must be a point adjacent to a point outside the loop 
		// Then disconnect the circuit from that point , It's a path back , Then follow the steps 1 Try to expand the path 
		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;
}

Copy

Copyright notice ： This article is the original article of the blogger , Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116761.html Link to the original text ：https://javaforall.cn