#include<iostream>
#include<cstdlib>
using namespace std;

int x[101];
bool graph[101][101];


bool NextValueAbideByRule( int k,int nodeNum)
{
   
	int preNode;
	int currentNode;
	int i;
	while(1)
	{
		x[k] = div( (x[k]+1),(nodeNum + 1)).rem;
		if( x[k] == 0)   //如果找不到合法的結點
		{
			return false;
		}
		if( k == 1)
			return true;
		//接下來x[k]檢查合法性
		if( k > 1)
		{
			preNode = x[k-1];
			currentNode = x[k];

			for( i =1; i < k;i++) //判斷是否結點重復
			{
				if(x[k] == x[i])
					break;
			}//for
			if( i < k) continue;

			if( !graph[preNode][currentNode]) //判斷是否有邊與前一結點相連
				continue;
          	return true;
		}
		

	}//while
}

void OutPut(int nodeNum)
{
	int i;
	cout<<"--------------------"<<endl;
	for(i = 1; i<=nodeNum; i++)
	{
		cout<<x[i]<<"   ";
	}
	cout<<endl;

}

void HamiltonCicle( int nodeNum)
{
	int k =1;
	int firstNode;
	int currentNode;
	int num = 0;

	while( k > 0 )
	{
		if(NextValueAbideByRule( k,nodeNum))
		{
			if( k == nodeNum)
			{
			      firstNode = x[1];
	              currentNode = x[k];
				if(graph[firstNode][currentNode])//如果最后一個結點和第一個結點有邊相連接
				{
				    num++;
					OutPut(nodeNum);
				}
			}
			else
				k++;
		}
		else
			k--;
	}
	if(num == 0)
		cout<<"cannot find a hamiltonCircle"<<endl;
}

void main()
{
	
   int 	nodesNum = 5;
	graph[1][1]=0; graph[1][2]=1;  graph[1][3]=0; graph[1][4]=1;  graph[1][5]=1;
	graph[2][1]=1; graph[2][2]=0;  graph[2][3]=1; graph[2][4]=1;  graph[2][5]=1;
	graph[3][1]=0; graph[3][2]=1;  graph[3][3]=0; graph[3][4]=1;  graph[3][5]=0;
	graph[4][1]=1; graph[4][2]=1;  graph[4][3]=1; graph[4][4]=0;  graph[4][5]=0;
	graph[5][1]=1; graph[5][2]=1;  graph[5][3]=0; graph[5][4]=0;  graph[5][5]=0;
	/*int i,j;
	int nodesNum;
	cout<<"please input the number of the nodes"<<endl;
	cin>>nodesNum;
	cout<<"please input the graph"<<endl;
	for( i = 1; i<=nodesNum; i++)
		for( j = 1; j <= nodesNum; j++)
			  cin>>graph[i][j];*/

    HamiltonCicle(nodesNum);
	cout<<"inputing ends"<<endl;
	
}