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

#define INF 9999

// POINTERS/VERTEX
typedef struct vertex
{
    int name;
    struct vertex *neighbors;
    int numNeighbors;
    int S_distance;
} 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()
{
    // verificare daca sunt elemente in coada
    if (indexStack > 0)
    {
        int value = stack[0];
        for (int i = 0; i < indexStack - 1; i++)
        {
            stack[i] = stack[i + 1];
        }
        indexStack--;
        return value;
    }
    printf("Coada este goala!\n");
    return (int)0;
}

graphVertex readGraphVertex(const char *fileName, int *sursa)
{
    graphVertex graph;

    FILE *f = fopen(fileName, "r");
    if (f == NULL)
    {
        return graph;
    }

    fscanf(f, "%i %i %i", &(graph.numNodes), &(graph.numEdges), &(*sursa));
    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].neighbors = (vertex *)malloc(graph.numNodes * sizeof(vertex));
        graph.nodes[i].S_distance = INF;
    }

    for (int i = 0; i < graph.numEdges; i++)
    {
        int left;
        int right;
        fscanf(f, "%i %i", &left, &right);

        graph.nodes[left].neighbors[graph.nodes[left].numNeighbors] = graph.nodes[right];
        graph.nodes[left].numNeighbors++;
    }

    fclose(f);
    return graph;
}

void bfs_vertex(graphVertex graph, int startNode, bool *visited)
{
    push(startNode);
    graph.nodes[startNode].S_distance = 0;

    while (indexStack > 0)
    {
        int popped_node = pop_queue();
        visited[popped_node] = true;

        for (int i = 0; i < graph.nodes[popped_node].numNeighbors; i++)
        {
            if (visited[graph.nodes[popped_node].neighbors[i].name] == false)
            {
                graph.nodes[graph.nodes[popped_node].neighbors[i].name].S_distance = graph.nodes[popped_node].S_distance + 1;
                push(graph.nodes[popped_node].neighbors[i].name);
                visited[graph.nodes[popped_node].neighbors[i].name] = true;
            }
        }
    }

    for (int i = 1; i <= graph.numNodes; i++)
    {
        if (visited[i] == false)
        {
            graph.nodes[i].S_distance = -1;
        }
    }
}

void output_inFile(const char *filename, graphVertex graph)
{
    FILE *f = fopen(filename, "w");
    if (f == NULL)
    {
        printf("Nu -a putut deschide fisierul!");
        exit(1);
    }

    for (int i = 1; i < graph.numNodes; i++)
    {
        fprintf(f, "%d ", graph.nodes[i].S_distance);
    }
    fprintf(f, "%d", graph.nodes[graph.numNodes].S_distance);

    fclose(f);
}

int main()
{
    int S;
    graphVertex VGraph = readGraphVertex("bfs.in", &S);

    bool visited[100] = {0};
    bfs_vertex(VGraph, S, visited);
    output_inFile("bfs.out", VGraph);

    return 0;
}