Cod sursa(job #2809489)
Utilizator | Fazakas Alexandru sandifx68 | Data | 27 noiembrie 2021 09:45:33 |
---|---|---|---|
Problema | BFS - Parcurgere in latime | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.74 kb |
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bfs.in");
ofstream gg("bfs.out");
int n,m,s,v[100005],p[100005];
vector <int>g[100005];
queue <int>q;
int main()
{
int x,y;
f>>n>>m>>s;
for(int i=1;i<=n;i++)
p[i]=-1;
for(int i=1;i<=m;i++){
f>>x>>y;
if(x!=y){
g[x].push_back(y);
}
}
q.push(s);
v[s]=1;
p[s]=0;
while(!q.empty())
{
for(auto&a:g[q.front()])
if(v[a]!=1)
{
q.push(a);
v[a]=1;
p[a]=p[q.front()]+1;
}
q.pop();
}
for(int i=1;i<=n;i++){
gg<<p[i]<<" ";
}
}