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

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

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

int n;
int stack[100][2];
int indexStack = 0;
//am cam facut din stiva coada
void push(int value, int grad)
{
	if (indexStack < 100) {
		for (int i = indexStack; i > 0; i--) {
			stack[i][0] = stack[i - 1][0];
			stack[i][1] = stack[i - 1][1];
		}
		stack[0][0] = value;
		stack[0][1] = grad;
		indexStack++;
	} else
		printf("Dimensiune stiva depasita!\n");
}

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

void bfs_pointers(graphVertex graph, int startNode, int* visited, int grad)
{
	int ok = 0;
	if (visited[startNode] == -1) {
		//printf("%d ", startNode);
		visited[startNode] = grad;
		for (int i = 0; i < graph.nodes[startNode].numNeighbors; i++)
			if ((visited[graph.nodes[startNode].neighbors[i]->name]) == (-1)) {
				push(graph.nodes[startNode].neighbors[i]->name, grad + 1);
				/*graph.nodes[graph.nodes[startNode].neighbors[i]->name].tata = startNode;
                graph.nodes[graph.nodes[startNode].neighbors[i]->name].grad = graph.nodes[startNode].grad + 1;*/
			}
	}
	if (indexStack > 0) {
		int grade;
		int w = pop(&grade);
		bfs_pointers(graph, w, visited, grade);
	}
}

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%i", &(graph.numNodes), &(graph.numEdges), &n);
	graph.nodes = (vertex*)malloc(sizeof(vertex) * (graph.numNodes + 1));
	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;
		//graph.nodes[i].grad = -1;
	}
	for (int i = 0; i < graph.numEdges; i++) {
		int x, y;
		fscanf(f, "%i%i", &x, &y);
		graph.nodes[x].numNeighbors++;
		graph.nodes[x].neighbors = (vertex**)realloc(graph.nodes[x].neighbors, graph.nodes[x].numNeighbors * sizeof(vertex*));
		graph.nodes[x].neighbors[graph.nodes[x].numNeighbors - 1] = &(graph.nodes[y]);
		/*graph.nodes[y].numNeighbors++;
		graph.nodes[y].neighbors = (vertex**)realloc(graph.nodes[y].neighbors, graph.nodes[y].numNeighbors * sizeof(vertex*));
		graph.nodes[y].neighbors[graph.nodes[y].numNeighbors - 1] = &(graph.nodes[x]);*/
	}
	fclose(f);
	return graph;
}

int main()
{
	graphVertex graphV = readGraphVertex("bfs.in");
	/*for (int i = 1; i <= graphV.numNodes; i++) {
		printf("%d ", graphV.nodes[i].numNeighbors);
	}*/
	int grade = 0;
	int* visited = (int*)malloc(sizeof(int) * (graphV.numNodes + 1));
	for (int i = 1; i <= graphV.numNodes; i++) visited[i] = -1;
	//printf("%d\n", n);
	//graphV.nodes[n].grad = 0;
	bfs_pointers(graphV, n, visited, 0);
	FILE* g = fopen("bfs.out", "w");
	for (int i = 1; i <= graphV.numNodes; i++)
		fprintf(g, "%d ", visited[i]);
	fclose(g);
	/*for (int i = 1; i <= graphV.numNodes; i++)
		printf("%d ", visited[i]);*/
	return 0;
}