#define _CRT_SECURE_NO_WARNINGS
#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 stack[100];
int indexStack = 0;

void push(int value)
{
	if (indexStack < 100)
		stack[indexStack++] = value;
	else
		printf("Dimensiune stiva depasita!\n");
}
int pop_queue()
{
	int value;
	if (indexStack > 0)
	{
		value = stack[0];
		for (int i = 0; i < indexStack - 1; i++)
			stack[i] = stack[i + 1];
		indexStack--;
		stack[indexStack] = 0;
		return value;
	}
	printf("Coada este goala");
	return (int)0;
}
graphVertex readGraphVertex(const char* fileName,int *startNode)
{
	graphVertex graph;
	graph.numEdges = 0;
	graph.numNodes = 0;
	int x = 0, nr;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	fscanf(f, "%i%i%i", &(graph.numNodes), &(graph.numEdges),&(*startNode));
	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 = 0;
		graph.nodes[i].neighbors = NULL;
		graph.nodes[i].weights = -1;
	}
	graph.nodes[*startNode-1].weights = 0;
	int vecini[500][500];
	for (int i = 0; i < graph.numEdges; i++)
	{
		fscanf(f, "%d %d", &x, &nr); 
		vecini[x-1][graph.nodes[x-1].numNeighbors]=nr-1;
		graph.nodes[x-1].numNeighbors++;
	}
	for (int i = 0; i < graph.numNodes; i++)
	{
          graph.nodes[i].neighbors = (vertex**)malloc(graph.nodes[i].numNeighbors * sizeof(vertex*));
		for(int j=0;j<graph.nodes[i].numNeighbors;j++)
			graph.nodes[i].neighbors[j] = &graph.nodes[vecini[i][j]];
	}
	fclose(f);
	return graph;
}
void bfs_vertex(graphVertex graph, int startNode, int* visited)
{
	push(startNode);
	int currentNode;
	while (indexStack)
	{
		currentNode = pop_queue();
		printf("%d ", currentNode);
		visited[currentNode] = 2;
		for (int i = 0; i < graph.nodes[currentNode].numNeighbors; i++)
		{
			if (visited[graph.nodes[currentNode].neighbors[i]->name] == 0)
			{
				push(graph.nodes[currentNode].neighbors[i]->name);
				visited[graph.nodes[currentNode].neighbors[i]->name] = 1;
			}
		}
	}
}
void bfs_pointers(graphVertex graph, int startNode, int* visited,char*filename)
{
	push(startNode);
	int currentNode=0;
	int prevNode=0;
	while (indexStack)
	{
		prevNode = currentNode;
		currentNode = pop_queue();
		int x = graph.nodes[prevNode].weights;
		if (currentNode != startNode && visited[currentNode]!=2)
		graph.nodes[currentNode].weights = graph.nodes[prevNode].weights + 1;
		visited[currentNode] = 2;
		for (int i = 0; i < graph.nodes[currentNode].numNeighbors; i++)
		{
			if (visited[graph.nodes[currentNode].neighbors[i]->name] == 0)
			{
				push(graph.nodes[currentNode].neighbors[i]->name);
				visited[graph.nodes[currentNode].neighbors[i]->name] = 1;
			}
		}
	}
	FILE* f = fopen(filename, "w");
	for (int i = 0; i < graph.numNodes; i++)
	{
		fprintf(f, "%d", graph.nodes[i].weights);
		if (i != graph.numNodes - 1)
		{
			fprintf(f, " ");
		}

	}
	fclose(f);
}
int main()
{
	graphVertex graph;
	int S;
	graph = readGraphVertex("bfs.in", &S);
	int visited[100] = { 0 };
	//bfs_vertex(graph, S, visited);
	bfs_pointers(graph, S-1, visited, "bfs.out");
}