Pagini recente » Borderou de evaluare (job #343706) | Cod sursa (job #1373749)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
#define foor(it,v) for(it=v.begin();it!=v.end();++it)
#define nmax 100010
int n,m,start,x,y,i;
vector <int> G[nmax];
int dist[nmax];
queue<int> q;
void bfs(int start)
{
int nod;
vector<int>::iterator it;
dist[start]=0;
q.push(start);
while(!q.empty())
{
nod=q.front();
q.pop();
foor(it,G[nod]) if(dist[*it]==-1)
{
dist[*it]=dist[nod]+1;
q.push(*it);
}
}
}
int main()
{
f>>n>>m>>start;
// dist.resize(n+1,-1);
// G.resize(n+1);
memset(dist,-1,sizeof dist);
for(;m;--m)
{
f>>x>>y;
G[x].push_back(y);
}
bfs(start);
for(i=1;i<=n;++i) g<<dist[i]<<' ';
return 0;
}