Cod sursa(job #3215268)

Utilizator AlexbzBujor Alexandru Alexbz Data 14 martie 2024 19:45:27
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

const int NMAX = 100001;

int n,m,S;
vector<int> lista[NMAX];
vector<int> vizitat(NMAX,0);
queue<int> coada;

void citire()
{
    fin >> n >> m >> S;
    for(int i = 1 ; i <= m ; i++)
    {
        int a,b;
        fin >> a >> b;
        lista[a].push_back(b);
    }
}

void bfs(int start)
{
    coada.push(start);
    vizitat[start] = 1;

    while(!coada.empty())
    {
        int nod_crt = coada.front();
        coada.pop();

        for(int i = 0 ; i < lista[nod_crt].size() ; i++)
            if(vizitat[lista[nod_crt][i]] == 0)
            {
                coada.push(lista[nod_crt][i]);
                vizitat[lista[nod_crt][i]]+=vizitat[nod_crt] + 1;
            }
    }
}

int main()
{
    citire();
    bfs(S);
    for(int i = 1 ; i <= n ; i++)
        fout << vizitat[i] - 1 << ' ';
}