Cod sursa(job #1049542)
Utilizator | Mezei Silviu Silviuss | Data | 7 decembrie 2013 14:55:29 |
---|---|---|---|
Problema | BFS - Parcurgere in latime | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.63 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int main()
{
vector<int> v[100001],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_back(s);u.size();u.erase(u.begin()))
for(i=0;i<v[u[0]].size();++i)
if(a[v[u[0]][i]]==-1)
{
a[v[u[0]][i]]=a[u[0]]+1;
u.push_back(v[u[0]][i]);
}
for(i=1;i<=n;++i)
fout<<a[i]<<" ";
}