Cod sursa(job #2666425)
Utilizator | Barbu Mariana Mari_Barbu | Data | 1 noiembrie 2020 19:58:18 |
---|---|---|---|
Problema | BFS - Parcurgere in latime | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
vector<int> v[100005];
int n,m,s,d[100005],x,y,i;
queue<int> q;
int main()
{
f >> n >> m >> s;
for(i = 0; i < m; i++)
{
f >> x >> y;
v[x].push_back(y);
}
d[s] = 1;
q.push(s);
while(q.size())
{
x = q.front();
q.pop();
for(auto j:v[x])
if(!d[j])
{
d[j] = d[x] + 1;
q.push(j);
}
}
for(i = 1; i <= n; i++)
g << d[i]-1 << ' ';
f.close();
g.close();
return 0;
}