#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "Graph.h"
#include "GraphPrivate.h"

static bool hasHamiltonianCircuit(Graph g);

static bool dfsHamiltonianCircuit(Graph g, Vertex v, bool *visited, int numVerticesLeft);

int main(void) {
	Graph g = GraphRead(stdin);
	
	printf("Graph:\n");
	GraphShow(g);

	bool answer = hasHamiltonianCircuit(g);
	printf("The graph %s a Hamiltonian Ciruit\n",
			answer ? "has" : "does not have");

	GraphFree(g);
}

static bool hasHamiltonianCircuit(Graph g) {
	

    if (g->nV < 3) {
        return false;
    }

    bool *visited = calloc(g->nV, sizeof(bool));

	return dfsHamiltonianCircuit(g, 0, visited, g->nV);
}

static bool dfsHamiltonianCircuit(Graph g, Vertex v, bool *visited, int numVerticesLeft) {
	visited[v] = true;
	numVerticesLeft--;

	if (numVerticesLeft == 0 && GraphIsAdjacent(g, v, 0)) {
		return true;
	}

	struct adjNode *curr = g->edges[v];
	for (; curr != NULL; curr = curr->next) {
		Vertex w = curr->v;
		if (!visited[w]) {
			if (dfsHamiltonianCircuit(g, w, visited, numVerticesLeft)) {
				return true;
			}
		}
	}

	visited[v] = false;
	return false;
}