/**
	Алгоритъм BFS
	Намира всички върхове, достижими от даден стартов връх s.

	Графът е представен чрез списъци на съседство. Върховете му са индексирани от 0 до n-1. graph[u] са съседите на u.

	parent[u] - родителят на u, по пътя до s.
		Вместо visited[] ще ползваме, че връх u е намерен, ако parent[u] != -1.

	dist[u] - разстоянието в брой върхове между s и u.

	Можем да намерим и дали свързан граф е двуоцветим:
		На реда, отбелязан със * ако parent[v] != -1 и dist[u] == dist[v], то графът не е двуоцветим.

	Функцията Show_path може да се използва и за останалите алгоритми с parent[].
*/

#include <vector>
#include <queue>
#include <iostream>
#define Inf 2000000000
using namespace std;

const int n = 9;

vector<int> graph[n] = { { 2, 3, 4, 7 }, { 2, 3, 5 }, { 0, 1, 8 }, { 0, 1, 6, 7 }, { 0, 6, 8 }, { 1, 7 }, { 3, 4 }, { 0, 3, 5 }, { 2, 4 } };

int dist[n];
int parent[n];

void BFS(int s)
{
	for (int i = 0; i < n; i++){ dist[i] = Inf; parent[i] = -1; }

	dist[s] = 0;
	parent[s] = s;

	queue<int> q;
	q.push(s);

	while (!q.empty())
	{
		int u = q.front();
		q.pop();

		for (int v : graph[u])if (parent[v] == -1){ dist[v] = 1 + dist[u]; parent[v] = u; q.push(v); } // *
	}
	
	parent[s] = -1;
}

void Show_Path(int u)
{
	if (u == -1) return;
	Show_Path(parent[u]);
	cout << u << " ";
}

int main()
{
	BFS(0);

	for (int i = 0; i < n; i++)cout << parent[i] << " ";
	cout << endl;

	return 0;
}