/* Hamiltonian Path Finding.
 * If each vertex of a simple graph has degree >= n/2
 * There must be Hamiltonian Path/Cycle
 * Algorithm go like this:
 * Step 1: Init a path, add start point in
 * Step 2: Find any unused vertex which is reachable 
 *         BOTH from the head of the path and the tail of the path !!Attention: BOTH!!
 *         and insert it front head or after tail
 * Step 3: Continue Step2 until cannot find any more
 * Step 4: The formed path can become a cycle, i.e. path = a[1]a[2]...a[m],
           there must exist ai, s.t. edge(a[1],a[i+1]) && edge(a[i],a[m])
		   The path can be changed to a[1]...a[i]a[m]...a[i+1]a[1]
 * Step 5: If the cycle contains all the vertices, we've done.
           Otherwise, for any unused point P, there must be some edge(a[k],P)
		   Reform the cycle to be a path like Pa[k]...a[end]a[begin]..a[k-1]
 * Step 6: Go to Step 2
 *
 * Linked List are used for faster reverse and insert
 * To Reverse a linked list, simply swap each node's (Previous, Next)
 * Good Practice!
 */
bool  m[1005][1005]={0};	//Graph Map m
int   vis[1005],n;			
int L[1005],R[1005],X[1005],root,count;
void FindHamiltonCycle()	//check connectivity first
{
	memset(vis,0,sizeof(vis));
	root=count=0;
	X[++count]=1;
	L[count]=root; R[root]=count;
	L[root]=count; R[count]=root;
	vis[1]=true;
 
	bool updated;
	int  head,headPos,newHead;
	int  tail,tailPos,newTail;
	int  start,addin,temp;
	while(1)
	{		
		do {
			head=X[R[root]]; headPos=R[root]; updated=false;
			tail=X[L[root]]; tailPos=L[root]; updated=false;
			for(int i=1;i<=n;i++) if(!vis[i]&&m[head][i]&&m[tail][i])
			{
				newHead=i;				
				vis[newHead]=updated=true;
				X[++count]=newHead;
				R[count]=headPos; L[headPos]=count;				
				L[count]=root; R[root]=count; 
				break;
			}			
		} while(updated);
 
		head=X[R[root]]; tail=X[L[root]]; 
		headPos=R[root]; tailPos=L[root];
		for(int ptr=R[root];ptr!=root;ptr=R[ptr])
		{
			if(m[head][X[R[ptr]]] && m[tail][X[ptr]]) {				
				start=R[ptr];
				while(1) {
					temp=L[start];
					L[start]=R[start];
					R[start]=temp;
					if(L[start]==root) {
						L[start]=ptr;
						R[R[ptr]]=root;
						L[root]=R[ptr];
						R[ptr]=start;
						break;
					} else start=L[start];
				}				
				break;
			}
		}		
		if(count==n) break;
		else {
			for(int i=1;i<=n;i++) if(!vis[i]) { addin=i; break; };
			for(int ptr=R[root];ptr!=root;ptr=R[ptr])
			{
				if(m[X[ptr]][addin]) {		
					X[++count]=addin;					
					vis[addin]=true;
					tailPos=L[root]; headPos=R[root];	
					R[root]=count; 
					if(L[ptr]!=root) { 
						L[root]=L[ptr]; R[L[ptr]]=root;
						R[tailPos]=headPos; L[headPos]=tailPos;
					}
					L[count]=root; R[count]=ptr;
					L[ptr]=count;					
					break;
				}
			}			
		}
	}
	printAns(1);
}

/* Hamiltonian Path Finding. * If each vertex of a simple graph has degree >= n/2 * There must be Hamiltonian Path/Cycle * Algorithm go like this: * Step 1: Init a path, add start point in * Step 2: Find any unused vertex which is reachable * BOTH from the head of the path and the tail of the path !!Attention: BOTH!! * and insert it front head or after tail * Step 3: Continue Step2 until cannot find any more * Step 4: The formed path can become a cycle, i.e. path = a[1]a[2]...a[m], there must exist ai, s.t. edge(a[1],a[i+1]) && edge(a[i],a[m]) The path can be changed to a[1]...a[i]a[m]...a[i+1]a[1] * Step 5: If the cycle contains all the vertices, we've done. Otherwise, for any unused point P, there must be some edge(a[k],P) Reform the cycle to be a path like Pa[k]...a[end]a[begin]..a[k-1] * Step 6: Go to Step 2 * * Linked List are used for faster reverse and insert * To Reverse a linked list, simply swap each node's (Previous, Next) * Good Practice! */ bool m[1005][1005]={0}; //Graph Map m int vis[1005],n; int L[1005],R[1005],X[1005],root,count; void FindHamiltonCycle() //check connectivity first { memset(vis,0,sizeof(vis)); root=count=0; X[++count]=1; L[count]=root; R[root]=count; L[root]=count; R[count]=root; vis[1]=true; bool updated; int head,headPos,newHead; int tail,tailPos,newTail; int start,addin,temp; while(1) { do { head=X[R[root]]; headPos=R[root]; updated=false; tail=X[L[root]]; tailPos=L[root]; updated=false; for(int i=1;i<=n;i++) if(!vis[i]&&m[head][i]&&m[tail][i]) { newHead=i; vis[newHead]=updated=true; X[++count]=newHead; R[count]=headPos; L[headPos]=count; L[count]=root; R[root]=count; break; } } while(updated); head=X[R[root]]; tail=X[L[root]]; headPos=R[root]; tailPos=L[root]; for(int ptr=R[root];ptr!=root;ptr=R[ptr]) { if(m[head][X[R[ptr]]] && m[tail][X[ptr]]) { start=R[ptr]; while(1) { temp=L[start]; L[start]=R[start]; R[start]=temp; if(L[start]==root) { L[start]=ptr; R[R[ptr]]=root; L[root]=R[ptr]; R[ptr]=start; break; } else start=L[start]; } break; } } if(count==n) break; else { for(int i=1;i<=n;i++) if(!vis[i]) { addin=i; break; }; for(int ptr=R[root];ptr!=root;ptr=R[ptr]) { if(m[X[ptr]][addin]) { X[++count]=addin; vis[addin]=true; tailPos=L[root]; headPos=R[root]; R[root]=count; if(L[ptr]!=root) { L[root]=L[ptr]; R[L[ptr]]=root; R[tailPos]=headPos; L[headPos]=tailPos; } L[count]=root; R[count]=ptr; L[ptr]=count; break; } } } } printAns(1); }