Cod sursa(job #2377851)

Utilizator vcerneaCernea Victor vcernea Data 11 martie 2019 11:40:56
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include<cstdio>
#include<vector>
#include<cstring>
int n , m , s , L;
const int NMAX = 100000;
std :: vector <int>v[NMAX + 1];
int G[NMAX + 1], S[NMAX + 1], Cost[NMAX + 1];
 
void BFS(int nod)
{
    int i, j;
 
    memset(Cost, -1, sizeof(Cost));
    L = 1;
    Cost[nod] = 0;
    S[L] = nod;
 
    for (i = 1; i <= L; i++)
        for (j = 0; j < G[S[i]]; j++)
            if (Cost[v[S[i]][j]] == -1)
            {
                S[++L] = v[S[i]][j];
                Cost[S[L]] = Cost[S[i]] + 1;
            }
}
int main()
{
  int x ,y;
  freopen("bfs.in","r",stdin);
  freopen("bfs.out","w",stdout);
  scanf("%d%d%d",&n,&m,&s);
  for(int i = 1; i <= m ; i ++)
  {
    scanf("%d%d",&x,&y);
    v[x].push_back(y);
  }
  for (int i = 1; i <= n; i++)
        G[i] = v[i].size();
 
    BFS(s);
 
    for (int i = 1; i <= n; i++)
        printf("%d ", Cost[i]);
    printf("\n");
 
    return 0;
}