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

//POINTERS/VERTEX
typedef struct vertex {
	int name;
	struct vertex** neighbors;
	int numNeighbors;
	int cost;
} 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;
}

void bfs(graphVertex graph, int startNode)
{
	int queue[500000], i = 0, j = 0;
	queue[j] = startNode - 1;
	while (i <= j) {
		if (graph.nodes[queue[i]].name - queue[i] == 0) {
			graph.nodes[queue[i]].name = -1;
			for (int k = 0; k < graph.nodes[queue[i]].numNeighbors; k++) {
				if (graph.nodes[queue[i]].neighbors[k]->name != -1 && graph.nodes[queue[i]].neighbors[k]->cost == 0) {
					queue[++j] = graph.nodes[queue[i]].neighbors[k]->name;
					graph.nodes[queue[j]].cost = graph.nodes[queue[i]].cost + 1;
				}
			}
		}
		i++;
	}
	for (i = 0; i < graph.numNodes; i++) {
		if (graph.nodes[i].name != -1) graph.nodes[i].cost = -1;
	}
	FILE* o = fopen("bfs.out", "w");
	if (o == NULL) return;
	for (i = 0; i < graph.numNodes; i++) {
		fprintf(o, "%d ", graph.nodes[i].cost);
		//printf("%d\t%d\t%d\n", i, (graph.nodes[i].name != -1 ? 0 : 1), graph.nodes[i].cost);
	}
	fclose(o);
}

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

	fscanf(f, "%i %i %i\n", &(graph.numNodes), &(graph.numEdges), start);
	graph.nodes = (vertex*)malloc(sizeof(vertex) * graph.numNodes);
	if (graph.nodes == NULL)
		return graph;
	for (int i = 0; i < graph.numNodes; i++) {
		graph.nodes[i].name = i;
		graph.nodes[i].numNeighbors = graph.nodes[i].cost = 0;
		graph.nodes[i].neighbors = NULL;
	}
	int a, b;
	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "%i %i", &a, &b);
		a--;
		b--;
		if (graph.nodes[a].numNeighbors == 0) {
			graph.nodes[a].neighbors = (vertex**)malloc(sizeof(vertex*));
		}
		graph.nodes[a].neighbors = (vertex**)realloc(graph.nodes[a].neighbors, sizeof(vertex**) * (++graph.nodes[a].numNeighbors));
		graph.nodes[a].neighbors[graph.nodes[a].numNeighbors - 1] = &(graph.nodes[b]);
		//&(graph.nodes[b]);
	}
	fclose(f);
	return graph;
}

int main()
{
	//POINTERS/VERTEX
	int start;
	graphVertex graphV = readGraphVertex("bfs.in", &start);

	bfs(graphV, start);
	return 0;
}