#define _CRT_SECURE_NO_WARNINGS

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

typedef struct edge {

	int left;
	int right;
}edge;

typedef struct graphEdges {

	int nr_noduri;
	int nr_edges;
	edge* lista_edge;

	int nod_start;
}graphEdges;

typedef struct node {

	int nod;
	struct node* next;
}node;

void pushCoada(node*& head, node*& tail, int element)
{
	node* temp = (node*)malloc(sizeof(node));
	if (temp == NULL)
	{
		printf("error push coada");
		return;
	}

	temp->nod = element;
	if (head == NULL)
	{
		temp->next = NULL;
		head = tail = temp;
	}
	else
	{
		temp->next = NULL;
		tail->next = temp;
		tail = temp;
	}
}

void popCoada(node*& head, node*& tail)
{
	node* aux = head;
	head = head->next;
	free(aux);
}

graphEdges citeste_edges(const char* filename)
{
	FILE* ptr = fopen(filename, "r");
	if (ptr == NULL)
	{
		printf("fisier nedeschis aici edges citire");
	}

	graphEdges graphE;
	fscanf(ptr, "%d %d %d", &graphE.nr_noduri, &graphE.nr_edges, &graphE.nod_start);
	graphE.lista_edge = (edge*)malloc(sizeof(edge) * graphE.nr_edges);
	for (int i = 0; i < graphE.nr_edges; i++)
	{
		fscanf(ptr, "%d %d", &graphE.lista_edge[i].left, &graphE.lista_edge[i].right);
	}
	fclose(ptr);

	return graphE;
}

void ordonare(graphEdges* graphE)
{
	for(int i=0;i<(*graphE).nr_noduri;i++)
		for (int j = i+1; j < (*graphE).nr_noduri; j++)
			if ((*graphE).lista_edge[i].left > (*graphE).lista_edge[j].left)
			{
				edge aux = (*graphE).lista_edge[i];
				(*graphE).lista_edge[i] = (*graphE).lista_edge[j];
				(*graphE).lista_edge[j] = aux;
			}
}

void BFS_net(graphEdges graphE, int nod_curent, int* visited, node*& head, node*& tail, int* array)
{
	int i = 0;
	while (nod_curent != graphE.lista_edge[i].left)
		i++;

	if (visited[nod_curent - 1] == 0)
	{
		pushCoada(head, tail, nod_curent);
		array[nod_curent - 1] = 0;
		visited[nod_curent - 1] = 1;
	}
	do
	{
		while (nod_curent == graphE.lista_edge[i].left)
		{
			if (visited[graphE.lista_edge[i].right - 1] == 0)
			{
				pushCoada(head, tail, graphE.lista_edge[i].right);
				visited[graphE.lista_edge[i].right - 1] = 1;
				array[graphE.lista_edge[i].right - 1] = array[nod_curent - 1] + 1;
			}
			i++;
		}
		popCoada(head, tail);
		if (head == NULL)
			break;
		BFS_net(graphE, head->nod, visited, head, tail, array);

	} while (head != NULL);
	
}

int main()
{
	graphEdges graph1 = citeste_edges("bfs.in");
	node* head2 = NULL, * tail2 = NULL;
	int* visited6 = (int*)malloc(sizeof(int) * graph1.nr_noduri);
	memset(visited6, 0, sizeof(int) * (graph1.nr_noduri+1));
	int *array = (int*)malloc(sizeof(int) * graph1.nr_noduri);
	memset(array, -1, sizeof(int) * (graph1.nr_noduri + 1));
	ordonare(&graph1);
	BFS_net(graph1, graph1.nod_start, visited6, head2, tail2, array);

	FILE* ptr = fopen("bfs.out", "w");
	for (int i = 0; i < graph1.nr_noduri - 1; i++)
	{
		fprintf(ptr, "%d ", array[i]);
	}
	fprintf(ptr, "%d", array[graph1.nr_noduri - 1]);
	fclose(ptr);
}