Cod sursa(job #2595502)

Utilizator mihaibreabanBreaban Mihai mihaibreaban Data 7 aprilie 2020 20:32:15
Problema BFS - Parcurgere in latime Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
vector<vector<int>> G;
int main()
{
    const int k = 100000;
    int N, M, S, sol[k] = {}, x, y;
    f >> N >> M >> S;
    G = vector<vector<int>>(N + 1);
    while(f >> x >> y)
        G[x].push_back(y);

    int coada[k] = {}, viz[k] = {}, inc = 1, Sf = 1, l = 1;
    coada[1] = S;
    viz[S] = 1;
    while(inc <= Sf){
        int nc = coada[inc];
        for(int j: G[nc])
        if(viz[j] == 0){
            Sf++;
            coada[Sf] = j;
            sol[j] = sol[nc] + 1;
            viz[j] = 1;
        }
        inc++;
    }
    for(int j = 1; j <= N; j++)
        if(viz[j] == 0 and j != S)
            sol[j] = -1;

    for(int j = 1; j <= N; j++)
        g << sol[j] << ' ';
    return 0;
}