#include <stdio.h>
#include <stdlib.h>
#include <string.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 queue[10001];
int indexQueue = 0;

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

int pop()
{
	if (indexQueue > 0) {
		int value = queue[0];
		for (int i = 0; i < indexQueue - 1; i++)
			queue[i] = queue[i + 1];
		queue[indexQueue] = 0;
		indexQueue--;
		return value;
	}
	printf("Stiva este goala!\n");
	return (int)0;
}
int source;
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), &source);
	graph.nodes = (vertex*)malloc(sizeof(vertex) * (graph.numNodes + 1));
	if (graph.nodes == NULL)
		return graph;
	for (int i = 1; i <= graph.numNodes; i++) {
		graph.nodes[i].name = i;
		graph.nodes[i].numNeighbors = 0;
		graph.nodes[i].weights = -1;
		graph.nodes[i].neighbors = NULL;
		graph.nodes[i].neighbors = (vertex**)malloc(sizeof(vertex*));
	}
	int x, y, k;
	for (int i = 0; i < graph.numEdges; i++) {  //
		fscanf(f, "%d%d", &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] = (vertex*)malloc(sizeof(vertex));
		graph.nodes[x].neighbors[graph.nodes[x].numNeighbors - 1]->name = y;
		k++;
	}
	fclose(f);
	return graph;
}

void bfs_vertex(graphVertex graph, int startNode, int* visited)
{
	visited[startNode] = 1;
	graph.nodes[startNode].weights = 0;
	push(startNode);
	int value = startNode;
	while (indexQueue != 0) {
		value = queue[0];
		for (int i = 0; i < graph.nodes[value].numNeighbors; i++) {
			if (visited[graph.nodes[value].neighbors[i]->name] != 1) {
				graph.nodes[graph.nodes[value].neighbors[i]->name].weights = graph.nodes[value].weights + 1;
				visited[graph.nodes[value].neighbors[i]->name] = 1;
				push(graph.nodes[value].neighbors[i]->name);
			}
		}
		pop();
	}
	FILE* g = fopen("bfs.out", "w");
	for (int i = 1; i <= graph.numNodes; i++) {
		fprintf(g, "%d ", graph.nodes[i].weights);
	}
}

int main(int argc, char** argv)
{
	graphVertex graph = readGraphVertex("bfs.in");
	int visited[100] = {0};
	bfs_vertex(graph, source, visited);
}