775 - Hamiltonian Cycle

[drewsome]

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]

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

waiting for reply....

[asif_rahman0]

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]

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]

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???

[helloneo]

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]

thnx helloneo.
but really stupid coz didnt notice it before:(

[nafeeur_kuet]

Giving Runtime Error!!!
But Why??

Code: Select all

//Removed

[brianfry713]

Your code won't work if n >= 10

[nafeeur_kuet]

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
#define READ(f) freopen(f, "r", stdin)
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()
{
    //READ("in.txt");
    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]

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';

[jddantes]

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;
vector<vector<int>> adjMat;

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;
		if(adjMat[node][i]){
			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
// 	// 	if(!adjMat[s.node][s.loopCtr]){
// 	// 		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;
		}

		if(adjMat[s.node][s.loopCtr]){
			st.push(package(s.start, s.loopCtr, s.len+1));
			continue;
		}

	}
}

int main(){
	while(!cin.eof()){
		cin >> N;
		adjMat.assign(N+50, vector<int>(N+50, 0));
		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--;
			adjMat[a][b] = adjMat[b][a] =1 ;
		}

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

	}
	return 0;
}