Cod sursa(job #1947120)

Utilizator gabriel.bjgGabriel b. gabriel.bjg Data 30 martie 2017 19:18:41
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp 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");

typedef struct _NOD {
    vector <int> neighbours;
    bool visited = false;
    int cost = -1;
}NOD, *PNOD;

NOD nodes[100005];

int main()
{
    int n, m, s, i, x, y;
    queue <int> Q;

    fin >> n >> m >> s;

    for (i = 0; i < m; i++)
    {
        fin >> x >> y;
        nodes[x].neighbours.push_back(y);
    }

    Q.push(s);
    nodes[s].visited = true;
    nodes[s].cost = 0;
    while (!Q.empty())
    {
        x = Q.front();
        for (int i : nodes[x].neighbours)
        {
            if (!nodes[i].visited)
            {
                Q.push(i);
                nodes[i].visited = true;
                nodes[i].cost = nodes[x].cost + 1;
            }
        }
        Q.pop();
    }

    for (i = 1; i <= n; i++)
        fout << nodes[i].cost << " ";

    return 0;
}