## 775 - Hamiltonian Cycle

Moderator: Board moderators

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

### 775 - Hamiltonian Cycle

Hi,

I am trying to solve 775 using simple backtracking. I've also tried pruning using BFS to make sure there was still a path back to the start vertex at each step. I am getting TLE.. please help!

Thanks,
- Andrew

Code: Select all

``````#include <iostream>
#include <map>
#include <stdio.h>
#include <set>
using namespace std;

int nv;

map<int, bool> seen;
map< int, set<int> > graph;
int s[1024];
int sp;
bool fnd;

void findHam(int curr) {
if (fnd) return;

if (sp == nv+1) {
if (curr == 1) {
fnd = true;
cout << s[0];
for (int i = 1; i < sp; i++) cout << " " << s[i];
cout << endl;
}
return;
}

set<int>::iterator k;
for (k = graph[curr].begin(); k != graph[curr].end(); k++) {
if (seen[*k]) continue;

seen[*k] = true;
s[sp++] = *k;
findHam(*k);
seen[*k] = false;
sp--;
}

return;
}

int main() {
while (cin >> nv) {

graph.clear();

int n1, n2;
while (scanf("%d %d\n", &n1, &n2) >= 1) {
if (n1 == n2) continue;

graph[n1].insert(n2);
graph[n2].insert(n1);
}

char c; cin >> c;

s[0] = 1;
sp = 1;
seen.clear();
fnd = false;
findHam(1);

if (!fnd) cout << "N" << endl;

}

return 0;
}
``````

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 775....how to speed up my program???

i have faced TLE in this problem. so i wanna to get rid of this thing.
but i didnt found any better algo/process.
so plz tell me that how i can speed up this prboelm>>

here is my code:

Code: Select all

``````code removed
``````
Last edited by asif_rahman0 on Wed May 03, 2006 7:07 pm, edited 1 time in total.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
yet no reply. ok. no problem to me.

but i need some help to solve this problem.
Just suggest me how can i solve this problem ??? or any better algo??
plz help me for learning nothing else.

may be just two / three hints then i can make it full:)

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
you're program is pretty much same with mine .. except for nextvalue()..
what is that for..?

i just recursively search into 'i' wherever there exists path from 'k' and not visited yet..

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
ok helloneo i changed my code now. i did it first time but changed later.
now i think it seems ok according to ur idea. but i still TLE!!!

Code: Select all

``````code removed
``````
so where is the main fault???
Last edited by asif_rahman0 on Thu May 04, 2006 2:14 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
hello asif_rahman0..~

taking input is kind of strange ..
vertex id could be bigger than 10 ..
i don't think your code works for that..

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
thnx helloneo.
but really stupid coz didnt notice it before:(

nafeeur_kuet
New poster
Posts: 6
Joined: Sat Dec 20, 2014 5:19 am

### Re: 775 - Hamiltonian Cycle

Giving Runtime Error!!!
But Why??

Code: Select all

``````//Removed
``````
Last edited by nafeeur_kuet on Fri Jan 09, 2015 5:03 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 775 - Hamiltonian Cycle

Your code won't work if n >= 10
Check input and AC output for thousands of problems on uDebug!

nafeeur_kuet
New poster
Posts: 6
Joined: Sat Dec 20, 2014 5:19 am

### Re: 775 - Hamiltonian Cycle

Still giving RE!!! But why?? Please explain guru......

Code: Select all

``````#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cstdio>
#include <math.h>
#include <cctype>
#include <string>
#include <vector>
#include <limits>
#include <bitset>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <cstring>
#include <utility>
#include <iomanip>
#include <iterator>
#include <iostream>
#include <algorithm>

using namespace std;

#define V 30000
bool graph[V][V];
bool isSafe(int v, int node, int path[], int pos)
{
if (graph [ path[pos-1] ][ v ] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}

bool hamCycleUtil(int node,int path[], int pos)
{
int VV=node;
if (pos==VV)
{
if ( graph[ path[pos-1] ][ path[0] ] == 1 )
return true;
else
return false;
}
for (int v = 1; v < VV; v++)
{
if (isSafe(v, node, path, pos))
{
path[pos] = v;
if (hamCycleUtil (node, path, pos+1) == true)
return true;
path[pos] = -1;
}
}
return false;
}
bool hamCycle(int node)
{
int VV=node;
int *path = new int[VV];
for (int i = 0; i < VV; i++)
path[i] = -1;
path[0] = 0;
if ( hamCycleUtil(node, path, 1) == false )
{
printf("N\n");
return false;
}

for (int i = 0; i < VV; i++)
printf("%d ", path[i]+1);
printf("%d", path[0]+1);
printf("\n");
return true;
}

int main()
{
int node;
while(scanf("%d",&node)!=EOF)
{
getchar();
for(int y=0; y<=node+10; y++)
for(int z=0; z<=node+10; z++)
graph[y][z]=0;
char s[1000000];
while(gets(s))
{
if(s[0]=='%')
break;
else
{

int u=s[0]-'0';
int v=s[2]-'0';

u--;
v--;

graph[u][v]=1;
graph[v][u]=1;
}
}

hamCycle(node);
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 775 - Hamiltonian Cycle

brianfry713 wrote:Your code won't work if n >= 10
These lines are assuming u and v are a single char:
int u=s[0]-'0';
int v=s[2]-'0';
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 775 - Hamiltonian Cycle

Why is it RE? I've already tried implementing it with a stack.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

int N;

int toInt(string &str){
int cnt = 0;
for(auto itr = str.rbegin(); itr!=str.rend(); ++itr){
cnt *= 10;
cnt += *itr - '0';
}
// cout << "transformed " << str << " to " << cnt << endl;
return cnt;
}

vector<bool> cycle;
vector<int> trace;

bool found;

int tabs = -1;
void printTabs(){
for(int i = 0; i<tabs;i++) printf("\t");
}

void f(int start, int node, int len){
if(found) return;
tabs++;
// printTabs();printf("Got to %d %d %d\n", start, node, len);

if(node == start){
if(len == N){
found = true;
trace.push_back(node);
for(int i = 0; i<N+1; i++){
if(i) printf(" ");
printf("%d", trace[i]+1);
}
printf("\n");
trace.pop_back();
tabs--;
return;
} else if(len){
tabs--;
return;
}
}

if(cycle[node]){
tabs--;
return;
}

cycle[node] = true;
trace.push_back(node);
// printTabs();printf("reached %d\n", node);
for(int i = 0; i<N; i++){
if(i == node) continue;
f(start, i, len+1);
}
}

trace.pop_back();
cycle[node] = false;
tabs--;
}

class package{
public:
int start, node, len;
int loopCtr;
package(){
start = node = len = -1;
loopCtr = 0;
}
package(int S, int N, int L){
start = S;
node = N;
len = L;
loopCtr = 0;
}
package(int S, int N, int L, int ctr){
start = S;
node = N;
len = L;
loopCtr = ctr;
}

bool operator== (const package& other) const{
return start == other.start && node == other.node && len == other.len;
}
bool operator!= (const package& other) const{
return start == other.start && node == other.node && len == other.len;
}
};

stack<package> st;

// void run(int start, int node, int len){
// 	if(found) return;
// 	st.push(state(start, node, len));

// 	state solved;

// 	// while(!st.empty()){
// 	// 	state s = st.top();
// 	// 	if(s.start == s.node){
// 	// 		if(s.len == N){
// 	// 			found = true;

// 	// 			// Found soln
// 	// 			trace.push_back(node);
// 	// 			for(int i = 0; i<N+1; i++){
// 	// 				if(i) printf(" ");
// 	// 				printf("%d", trace[i]+1);
// 	// 			}
// 	// 			printf("\n");
// 	// 			trace.pop_back();

// 	// 			solved = s;
// 	// 			st.pop();
// 	// 			continue;
// 	// 		} else if(s.len){
// 	// 			solved = s;
// 	// 			st.pop();
// 	// 			continue;
// 	// 		}
// 	// 	}

// 	// 	if(cycle[s.node] && !s.loopCtr){
// 	// 		solved = s;
// 	// 		st.pop();
// 	// 		continue;
// 	// 	}

// 	// 	cycle[s.node] = true;
// 	// 	trace.push_back(s.node);

// 	// 	package next(s.start, s.loopCtr, s.len+1);

// 	// 	// end of recusion, return
// 	// 	if(s.loopCtr == N){
// 	// 		solved = s;
// 	// 		trace.pop_back();
// 	// 		cycle[s.node] = false;
// 	// 		st.pop();
// 	// 		continue;
// 	// 	}

// 	// 	// Skip same node
// 	// 	if(s.loopCtr == s.node){
// 	// 		st.pop_back();
// 	// 		next.loopCtr++;
// 	// 		st.push(next);
// 	// 		continue;
// 	// 	}

// 	// 	// Skip not adj
// 	// 		st.pop_back();
// 	// 		next.loopCtr++;
// 	// 		st.push(next);
// 	// 		continue;
// 	// 	}

// 	// 	if(solved != next){
// 	// 		st.push(next);
// 	// 		continue;
// 	// 	} else {
// 	// 		st.pop_back();
// 	// 		next.loopCtr++;
// 	// 		st.push(next);
// 	// 		continue;
// 	// 	}

// 	}
// }

void run(int start, int node, int len){
if(found) return;
st.push(package(start, node, len));
package solved;

while(!st.empty()){
package s = st.top();
st.pop();

if(found) continue;

// printTabs();printf("%d %d %d %d\n", s.start, s.node, s.len, s.loopCtr);

if(s.node == s.start){
if(s.len == N){
found = true;
trace.push_back(s.node);
for(int i = 0; i<N+1; i++){
if(i) printf(" ");
printf("%d", trace[i]+1);
}
printf("\n");
trace.pop_back();
tabs--;
continue;
} else if(len){
tabs--;
continue;
}
}

if(s.loopCtr == 0){
tabs++;
if(cycle[s.node]){
continue;
}
cycle[s.node] = true;
trace.push_back(s.node);
}

if(s.loopCtr == N){
trace.pop_back();
cycle[s.node] = false;
tabs--;
continue;
}

package next = s;
next.loopCtr++;

st.push(next);

if(s.node == s.loopCtr){
continue;
}

st.push(package(s.start, s.loopCtr, s.len+1));
continue;
}

}
}

int main(){
while(!cin.eof()){
cin >> N;
cycle.assign(N+50, false);
found = false;

string raw;
while(!cin.eof()){
cin >> raw;
if(raw == "%"){
// cout <<"breaking" << endl;
break;
}
int b;
cin >> b;
int a = toInt(raw);
// cout << "got " << raw << " " << b << endl;
a--;
b--;
}

for(int start = 0; start<N; start++){
trace.clear();
run(start, start, 0);
}
if(!found){
cout << "N\n";
}

}
return 0;
}
``````