Cod sursa(job #2193694)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 10 aprilie 2018 22:54:23
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <cstring>
#define MAX 100055
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
vector <int> vecini[MAX];
int n[MAX],cost[MAX],nr_vecini[MAX],q,p,x,y,r,k;
void BFS()
{
    memset(cost, -1, sizeof(cost));
    /// setam toate costurile -1;
    k=1;
    ///nr de elem din coada;
    cost[r]=0;
    n[k]=r;
    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<nr_vecini[n[i]]; j++)
        {
            if(cost[vecini[n[i]][j]]==-1)
            {
                k++;
                n[k]=vecini[n[i]][j];
                cost[n[k]]=cost[n[i]]+1;
            }
        }
    }
}
int main()
{
    cin >> q >> p >> r;
    for(int i=0; i<p; i++)
    {
        cin >> x >> y;
        vecini[x].push_back(y);
    }
    for(int i=1; i<=q; i++)
    {
        nr_vecini[i]=vecini[i].size();
    }
    BFS();
    for(int i=1; i<=q; i++)
    {
        cout << cost[i] << ' ';
    }
    return 0;
}