HDU 4337 King Arthur's Knights 它输出一个哈密顿电路

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;

}

版权声明：本文博主原创文章，博客，未经同意不得转载。