#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;

typedef struct node
{
	int element;
	struct node* next;
} listNode;

void insertNodeHeadOfList(listNode** listStart, int element)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	if (node == NULL)
	{
		printf("ERROR: CAN NOT ALLOCATE RAM\n");
		return;
	}
	node->next = *listStart;
	node->element = element;
	*listStart = node;
}

listNode* getNode(listNode* listNode, int poz)
{
	for (int i = 0; i < poz; i++)
	{
		listNode = listNode->next;
		if (listNode->next == NULL)
			break;
	}
	return listNode;
}

void insertNodeInList(listNode** listStart, int element, int poz)
{
	if (poz == 0)
	{
		insertNodeHeadOfList(listStart, element);
		return;
	}
	listNode* node = (listNode*)malloc(sizeof(listNode));
	if (node == NULL)
	{
		printf("ERROR: CAN NOT ALLOCATE RAM\n");
		return;
	}

	listNode* aux = getNode(*listStart, poz - 1);

	node->next = aux->next;
	node->element = element;
	aux->next = node;
}

void push(listNode** listStart, int element)
{
	listNode* copie = *listStart;
	int poz = 0;

	if (copie == NULL)
		insertNodeHeadOfList(listStart, element);
	else
	{
		while (copie != NULL)
		{
			copie = copie->next;
			poz++;
		}

		insertNodeInList(listStart, element, poz);
	}
}

int pop(listNode** listStart)
{
	if (*listStart == NULL)
		return;
	listNode* aux = (*listStart);
	int value = aux->element;
	*listStart = (*listStart)->next;
	return value;
}

void BFS(graphVertex* graph,int sursa, int** costuri, int* visited)
{
	visited[sursa] = 1;
	listNode* queue = NULL;
	push(&queue, sursa);
	(*costuri)[sursa] = 0;
	while (queue != NULL) {
		sursa = pop(&queue);
		visited[sursa] = 1;
		for (int j = 1; j <= graph->nodes[sursa]->numNeighbors; j++)
			if (!visited[graph->nodes[sursa]->neighbors[j]->name])
			{
				push(&queue, graph->nodes[sursa]->neighbors[j]->name);
				(*costuri)[graph->nodes[sursa]->neighbors[j]->name] = (*costuri)[sursa] + 1;
				visited[graph->nodes[sursa]->neighbors[j]->name] = 2;
				

			}
	}
}

printCosturi(int* costuri,int nr_costuri,char* filename)
{
	FILE* fout = fopen(filename, "w");
	if (fout == NULL)
	{
		printf("Eroare la deschiderea fisierului de iesire");
		exit(1);
	}

	int i;
	for (i = 1; i <= nr_costuri-1; i++)
		fprintf(fout, "%d ", costuri[i]);
	fprintf(fout, "%d", costuri[i]);

	fclose(fout);
}

vertex* vecin(graphVertex* graph, int val)
{
	for (int i = 1; i <= graph->numNodes; i++)
		if (graph->nodes[i]->name == val)
			return graph->nodes[i];

}

graphVertex* readGraph(char* filename, int *sursa)
{
	
	FILE* f = fopen(filename, "r");
	if (f == NULL)
	{
		printf("Eroare deschidere fisier");
		exit(1);
	}

	graphVertex *graph=(graphVertex*)malloc(sizeof(graphVertex));

	fscanf(f, "%d%d%d", &(graph->numNodes), &(graph->numEdges),sursa);

	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] = (vertex*)malloc(sizeof(vertex));
		graph->nodes[i]->name = i;
		graph->nodes[i]->numNeighbors = 0;
		graph->nodes[i]->neighbors = NULL;
	}

	int y, z,t;

	for (int i = 1; i <= graph->numNodes; i++)
	{
		fseek(f, 0, SEEK_SET);
		fscanf(f, "%d%d%d", &y, &z,&t);
		for (int j = 0; j < graph->numEdges; j++)
		{
			fscanf(f, "%d%d", &y, &z);
			if (y == i && y!=z)
				graph->nodes[i]->numNeighbors++;
		}
	}
	for (int i = 0; i <= graph->numNodes; i++)
		graph->nodes[i]->neighbors = (vertex**)malloc(sizeof(vertex*) * (graph->nodes[i]->numNeighbors+1));


	for (int i = 1; i <= graph->numNodes; i++)
	{
		int j = 1;
		fseek(f, 0, SEEK_SET);
		fscanf(f, "%d%d%d", &y, &z,&t);
		for (int k = 0; k < graph->numEdges; k++)
		{
			fscanf(f, "%d%d", &y, &z);
			if (y == i && y!=z)
			{
				graph->nodes[i]->neighbors[j] = vecin(graph, z);
				j++;
			}
		}
	}

	fclose(f);
	return graph;
}

int main()
{
	int sursa;
	graphVertex* graph = readGraph("bfs.in", &sursa);

	int* costuri = (int*)malloc(sizeof(int) * (graph->numNodes+1));
	for (int i = 0; i <= graph->numNodes; i++)
		costuri[i] = -1;

	listNode* queue = NULL;
	int* visited = (int*)calloc(graph->numNodes+1, sizeof(int));
	for (int i = 0; i <= graph->numNodes; i++)
		visited[i] = 0;
	push(&queue, sursa);
	BFS(graph,sursa,&costuri,visited);

	printCosturi(costuri,graph->numNodes, "bfs.out");
	return 0;
}