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

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

static bool hasCycle(Graph g);

static bool dfsHasCycle(Graph g, Vertex v, Vertex prev, bool *visited);

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

	bool answer = hasCycle(g);
	printf("The graph %s a cycle\n",
			answer ? "contains" : "does not contain");

	GraphFree(g);
}

static bool hasCycle(Graph g) {
	bool *visited = calloc(g->nV, sizeof(bool));

    bool answer = dfsHasCycle(g, 0, 0, visited);

	free(visited);
	return answer;
}

static bool dfsHasCycle(Graph g, Vertex v, Vertex prev, bool *visited) {
	visited[v] = true;
	printf("Visited %d\n", v);

	struct adjNode *curr = g->edges[v];
	for (; curr != NULL; curr = curr->next) {
		Vertex w = curr->v;
		if (w == prev) continue;
		if (visited[w]) {
			printf("Found a cycle going from %d to %d\n", v, w);
			return true;
		} else {
			if (dfsHasCycle(g, w, v, visited)) {
				return true;
			}
		}
	}

	return false;
}