Cod sursa(job #1051000)
Utilizator | Mezei Silviu Silviuss | Data | 9 decembrie 2013 16:20:41 |
---|---|---|---|
Problema | BFS - Parcurgere in latime | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int main()
{
vector<int> v[100001];
queue<int> u;
int n,m,s,i,j,a[100001];
fin>>n>>m>>s;
for(i=1;i<=n;++i)
a[i]=-1;
while(m)
{
fin>>i>>j;
v[i].push_back(j);
m--;
}
for(a[s]=0,u.push(s);u.size();u.pop())
for(i=0;i<v[u.front()].size();++i)
if(a[v[u.front()][i]]==-1)
{
a[v[u.front()][i]]=a[u.front()]+1;
u.push(v[u.front()][i]);
}
for(i=1;i<=n;++i)
fout<<a[i]<<" ";
}