Cod sursa(job #2629560)

Utilizator RaduQQTCucuta Radu RaduQQT Data 21 iunie 2020 15:10:42
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>





typedef struct listNode
{
	listNode* next;
	int el;
};

listNode* list[100300];

void insertNodeInList(listNode*& head, int el)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->el = el;

	if (head == NULL)
	{
		head = node;
		head->next = NULL;
		return;
	}

	node->next = head;
	head = node;
}

void push(listNode*& start, listNode*& finish,int el)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->el = el;

	if (start == NULL)
	{
		start = node;
		finish = node;
		finish->next = NULL;
		return;
	}
	finish->next = node;
	node->next = NULL;
	finish = finish->next;
}
void pop(listNode*& start, listNode*& finish)
{
	if (start == NULL)
		return;

	if (start->next == NULL)
		finish = NULL;
	listNode* aux = start;
	start = start->next;
	free(aux);
}
int n, m,rad;

int dist[100020];
bool viz[100021];

void bfs(listNode* start, listNode* finish)
{
	while (start != NULL)
	{
		listNode* aux = list[start->el];
		int anterior = start->el;
		

		pop(start, finish);
		while (aux != NULL)
		{
			if (!viz[aux->el])
			{
				dist[aux->el] = dist[anterior] + 1;
				push(start, finish, aux->el);
				viz[aux->el] = 1;
			}
			aux = aux->next;
		}
	}
}
int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	scanf("%d%d%d", &n, &m, &rad);
	for (int i = 1; i <= n; i++)
		list[i] = NULL;

	int a, b;
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &a, &b);
		insertNodeInList(list[a], b);
	}


	for (int i = 1; i <= n; i++)
		dist[i] = -1;
	dist[rad] = 0;


	listNode* start = NULL, *finish = NULL;
	push(start, finish, rad);
	viz[rad] = 1;
	bfs(start, finish);
	for (int i = 1; i <= n; i++)
		printf("%d ", dist[i]);
}