Cod sursa(job #2603325)

Utilizator bmc213Mihai Cosmin bmc213 Data 19 aprilie 2020 11:36:38
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int d[100005], n, m, S, i, x, y;
bool viz[100005];
vector <int> v[100005];
queue <int> Q;

void bfs()
{
    Q.push(S);
    viz[S] = 1;
    d[S] = 0;
    while(!Q.empty())
    {
        int k = Q.front();
        Q.pop();
        for(vector <int> :: iterator it = v[k].begin(); it != v[k].end(); ++ it)
        {
            if(!viz[*it])
            {
                Q.push(*it);
                d[*it] = d[k] + 1;
                viz[*it] = 1;
            }
        }
    }
}
int main()
{
    f >> n >> m >> S;
    for(i = 1; i <= m; ++ i)
    {
        f >> x >> y;
        v[x].push_back(y);
    }
    for(i = 1; i <= n; ++ i)
        d[i] = -1;
    bfs();
    for(i = 1; i <= n; ++ i)
        g << d[i] << " ";
    return 0;
}