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

// ADJACENCY MATRIX
typedef struct graphMatrix
{
	int **adjacencyMatrix;
	int numNodes;
} graphMatrix;

// EDGES
typedef struct edge
{
	int leftNode;
	int rightNode;
} edge;

typedef struct graphEdges
{
	edge *edges;
	int numNodes;
	int numEdges;
} graphEdges;

// POINTERS/VERTEX
typedef struct vertex
{
	int name;
	struct vertex **neighbors;
	int numNeighbors;
	//	int* weights;
} vertex;

typedef struct graphVertex
{
	int numNodes;
	int numEdges;
	vertex **nodes;
} graphVertex;

int stack[100];
int indexStack = 0;

void push(int value)
{
	if (indexStack < 100)
		stack[indexStack++] = value;
	else
		printf("Dimensiune stiva depasita!\n");
}

int pop()
{
	// verificare daca sunt elemente in stiva
	if (indexStack > 0)
	{
		int value = stack[--indexStack];
		stack[indexStack] = 0;
		return value;
	}
	printf("Stiva este goala!\n");
	return (int)0;
}

int tail[100];
int indexTail = 0;

void push_tail(int value)
{
	if (indexTail < 100)
		tail[indexTail++] = value;
	else
		puts("coada plina");
}

int pop_tail()
{
	if (indexTail > 0)
	{
		int k = tail[0];

		for (int i = 0; i < indexTail - 1; i++)
			tail[i] = tail[i + 1];

		tail[--indexTail] = 0;
		return k;
	}
	else
		puts("coada goala");
}

void bfs_matrix(graphMatrix graph, int startNode, int *visited)
{
	int n = graph.numNodes;
	push_tail(startNode);
	int k;
	while (indexTail > 0)
	{
		k = pop_tail();
		printf("%d ", k);
		visited[k] = 1;

		for (int i = 0; i < n; i++)
			if (graph.adjacencyMatrix[k][i] && visited[i] == 0)
			{
				push_tail(i);
				visited[i] = 1;
			}
	}
}

void dfs_matrix(graphMatrix graph, int currentNode, int *visited)
{

	int n = graph.numNodes;

	if (visited[currentNode] == 0)
	{
		printf("%d ", currentNode);
		visited[currentNode] = 1;
	}
	for (int i = 0; i < n; i++)
		if (graph.adjacencyMatrix[currentNode][i] && !visited[i])
		{
			dfs_matrix(graph, i, visited);
		}
}

graphMatrix readGraphMatrix(const char *fileName)
{
	FILE *f = fopen(fileName, "r");
	graphMatrix graph;
	graph.numNodes = 0;
	if (f == NULL)
		return graph;

	fscanf(f, "%d", &(graph.numNodes));
	int n = graph.numNodes;
	graph.adjacencyMatrix = (int **)malloc(graph.numNodes * sizeof(int *));

	for (int i = 0; i < n; i++)
		graph.adjacencyMatrix[i] = (int *)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			fscanf(f, "%d", &(graph.adjacencyMatrix[i][j]));

	// TODO

	fclose(f);
	return graph;
}

void bfs_edges(graphEdges graph, int startNode, int *visited)
{
	int n = graph.numEdges;
	push_tail(startNode);

	int k;

	while (indexTail > 0)
	{
		k = pop_tail();
		printf("%d ", k);
		visited[k] = 1;

		for (int i = 0; i < n; i++)
			if (graph.edges[i].leftNode == k && !visited[graph.edges[i].rightNode])
			{
				push_tail(graph.edges[i].rightNode);
				visited[graph.edges[i].rightNode] = 1;
			}
	}
}

void dfs_edges(graphEdges graph, int currentNode, int *visited)
{
	if (visited[currentNode] == 0)
	{
		printf("%d ", currentNode);
		visited[currentNode] = 1;
	}

	for (int i = 0; i < graph.numEdges; i++)
		if (graph.edges[i].leftNode == currentNode && !visited[graph.edges[i].rightNode])
		{
			dfs_edges(graph, graph.edges[i].rightNode, visited);
		}
}

graphEdges readGraphEdgeList(const char *fileName)
{
	graphEdges graph;
	graph.numEdges = 0;
	graph.edges = NULL;
	FILE *f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	// TODO

	fscanf(f, "%d", &(graph.numNodes));
	fscanf(f, "%d", &(graph.numEdges));

	graph.edges = (edge *)malloc(graph.numEdges * sizeof(edge));

	for (int i = 0; i < graph.numEdges; i++)
		fscanf(f, "%d %d", &(graph.edges[i].leftNode), &(graph.edges[i].rightNode));

	fclose(f);
	return graph;
}

void bfs_pointers(graphVertex graph, int startNode, int *visited)
{
	push_tail(startNode);
	int k;

	while (indexTail > 0)
	{
		k = pop_tail();

		printf("%d ", k);
		visited[k] = 1;

		for (int i = 0; i < graph.nodes[k]->numNeighbors; i++)
			if (visited[graph.nodes[k]->neighbors[i]->name] == 0)
			{
				push_tail(graph.nodes[k]->neighbors[i]->name);
				visited[graph.nodes[k]->neighbors[i]->name] = 1;
			}
	}
}

void dfs_pointers(graphVertex graph, int currentNode, int *visited)
{
	if (!visited[currentNode])
	{
		printf("%d ", currentNode);
		visited[currentNode] = 1;
	}

	for (int i = 0; i < graph.nodes[currentNode]->numNeighbors; i++)
	{
		if (visited[graph.nodes[currentNode]->neighbors[i]->name] == 0)
		{
			dfs_pointers(graph, graph.nodes[currentNode]->neighbors[i]->name, visited);
		}
	}
}

graphVertex readGraphVertex(const char *fileName)
{
	graphVertex graph;
	graph.numEdges = 0;
	graph.numNodes = 0;
	FILE *f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	fscanf(f, "%i%i", &(graph.numNodes), &(graph.numEdges));
	graph.nodes = (vertex **)malloc(sizeof(vertex *) * graph.numNodes);

	for (int i = 0; i < graph.numNodes; i++)
	{
		graph.nodes[i] = (vertex *)malloc(sizeof(vertex));
	}

	if (graph.nodes == NULL)
		return graph;
	for (int i = 0; i < graph.numNodes; i++)
	{
		graph.nodes[i]->name = i;
		graph.nodes[i]->numNeighbors = 0;
		graph.nodes[i]->neighbors = NULL;
	}

	graphEdges graphE = readGraphEdgeList(fileName);

	int *copii = (int *)malloc(graph.numNodes * sizeof(int));
	// int n = graph.numNodes;
	for (int i = 0; i < graph.numNodes; i++)
		copii[i] = 0;

	for (int i = 0; i < graphE.numEdges; i++)
		copii[graphE.edges[i].leftNode]++;

	/*  int left,right;
	 for (int i = 0; i < graph.numEdges; i++)
	 {
		 fscanf(f,"%d %d",left,right);
		 // TODO
		 for(int j=0;j<graph.numNodes;j++)

	 }*/
	fclose(f);

	for (int i = 0; i < graph.numNodes; i++)
	{
		graph.nodes[i]->name = i;
		graph.nodes[i]->numNeighbors = copii[i];
		graph.nodes[i]->neighbors = (vertex **)malloc(copii[i] * sizeof(vertex *));

		for (int j = 0; j < copii[i]; j++)
		{
			graph.nodes[i]->neighbors[j] = (vertex *)malloc(sizeof(vertex));
		}
	}

	for (int i = 0; i < graph.numNodes; i++)
	{
		int k = 0;
		for (int j = 0; j < graph.numEdges; j++)
		{
			if (i == graphE.edges[j].leftNode)
			{
				graph.nodes[i]->neighbors[k]->name = graphE.edges[j].rightNode;
				graph.nodes[i]->neighbors[k]->numNeighbors = copii[graphE.edges[j].rightNode];
				k++;
			}
		}
	}

	for (int i = 0; i < graph.numNodes; i++)
	{
		for (int j = 0; j < graph.nodes[i]->numNeighbors; j++)
			graph.nodes[i]->neighbors[j] = graph.nodes[graph.nodes[i]->neighbors[j]->name];
	}

	return graph;
}

int full(int *v, int n)
{
	for (int i = 0; i < n; i++)
		if (!v[i])
			return 0;

	return 1;
}

void DFS_pointers(graphVertex graph, int currentNode, int *visited, int **c)
{
	if (!visited[currentNode])
	{
		// printf("%d ", currentNode);
		visited[currentNode] = 1;
		(*c)[currentNode] = 1;
	}

	for (int i = 0; i < graph.nodes[currentNode]->numNeighbors; i++)
	{
		if (visited[graph.nodes[currentNode]->neighbors[i]->name] == 0)
		{
			DFS_pointers(graph, graph.nodes[currentNode]->neighbors[i]->name, visited, &(*c));
		}
	}
}

void DFS_infoarena(const char *file)
{
	graphVertex graph = readGraphVertex(file);

	int n = graph.numNodes;
	int *checked = (int *)malloc(n * sizeof(int));
	int *visited = (int *)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
	{
		checked[i] = 0;
		visited[i] = 0;
	}

	int conexe = 0;

	for (int i = 0; i < n && !full(checked, n); i++)
	{
		while (checked[i])
			i++;

		conexe++;
		DFS_pointers(graph, i, visited, &checked);

		/*	for (int j = 0; j < n; j++)
			printf("%d ", checked[j]);

			puts(" ");*/
	}

	FILE *f;
	f = fopen("dfs.out", "w");

	fprintf(f, "%d", conexe);

	fclose(f);
}

int main()
{
	// ADJACENCY MATRIX
	/*	graphMatrix graphM = readGraphMatrix("graphMatrix.txt");
		int visited[100] = {0}; // we assume fewer than 100 nodes
		dfs_matrix(graphM, 0, visited);
		printf("\n");
		int visited1[100] = {0}; // we assume fewer than 100 nodes
		bfs_matrix(graphM, 0, visited1);
		printf("\n");
		// EDGES
		graphEdges graphE = readGraphEdgeList("graphEdges.txt");
		int visited2[100] = {0}; // we assume fewer than 100 nodes
		dfs_edges(graphE, 0, visited2);
		printf("\n");
		int visited3[100] = {0}; // we assume fewer than 100 nodes
		bfs_edges(graphE, 0, visited3);
		printf("\n");
		// POINTERS/VERTEX
		graphVertex graphV = readGraphVertex("graphEdges.txt");
		int visited4[100] = {0}; // we assume fewer than 100 nodes
		dfs_pointers(graphV, 0, visited4);
		printf("\n");
		int visited5[100] = {0}; // we assume fewer than 100 nodes
		bfs_pointers(graphV, 0, visited5);
		printf("\n");*/

	DFS_infoarena("dfs.in");
	printf("\n\n\n");
	return 0;
}