Cod sursa(job #3372004)

Utilizator ifrimdragosIfrim Dragos ifrimdragos Data 2 noiembrie 2026 07:19:12
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

void bfs(int node , vector<vector<int>>& nodesneighbors , queue<int>& q , vector<int>& costfromstoindex)
{
    q.push(node);
    costfromstoindex[node] = 0;
    while(!q.empty())
    {
        int current = q.front();
        q.pop();
        int len = nodesneighbors[current].size();
        for (int i = 0 ; i < len ; i++)
        {
            int neighbor = nodesneighbors[current][i];
            if(costfromstoindex[neighbor] >= costfromstoindex[current] + 1)
            {
                costfromstoindex[neighbor] = costfromstoindex[current] + 1;
                q.push(neighbor);

            }
        }

    }

}

int main()
{
    int n , m , s;
    fin >> n >> m >> s;
    vector<vector<int>>nodesneighbors(n + 1);
    vector<int>costfromstoindex (n + 1 , INT_MAX);
    queue<int>q;

    for(int i = 1 ; i <= m; i++)
    {
        int node , neighbor;
        fin >> node >> neighbor;
        nodesneighbors[node].push_back(neighbor);

    }
    bfs(s,nodesneighbors , q , costfromstoindex);
    for(int i = 1 ; i <= n ; i++)
    {

        if(costfromstoindex[i] == INT_MAX)
        {
            costfromstoindex[i] = -1;
        }
        fout << costfromstoindex[i] << " " <<endl;
    }

    return 0;
}