Cod sursa(job #1741201)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 13 august 2016 12:20:05
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
using namespace std;
FILE *f1=fopen("bfs.in","r");
FILE *f2=fopen("bfs.out","w");
int n,m,s,i,j,v[100001],coada[100001],nrc;
struct nod{
    int inf;
    nod *urm;
}*L[100001];
void adaugsf(int val,nod *&vf){
     nod *q;
     q=new nod;
     q->inf=val;
     q->urm=vf;
     vf=q;
}
void cit(){
     int i,a,b;
     fscanf(f1,"%d%d%d",&n,&m,&s);
     for (i=1;i<=n;i++)
        L[i]=0;
     for (i=1;i<=m;i++){
        fscanf(f1,"%d%d",&a,&b);
        adaugsf(b,L[a]);
     }
     fclose(f1);
}
void bfs(){
    int i,x,p,u;
    nod *q;
    v[s]=1;p=u=1;
    coada[u]=s;
    while(p<=u){
        x=coada[p];
        q=L[x];
        while(q!=0){
            if (v[q->inf]==0){
                v[q->inf]=v[x]+1;
                u++;
                coada[u]=q->inf;
            }
            q=q->urm;
        }
        p++;
    }
}
int main(){
    cit();
    bfs();
    for (i=1;i<=n;i++)
        if (i==s) fprintf(f2,"0 ");
           else
            if (v[i]==0) fprintf(f2,"-1 ");
              else
                fprintf(f2,"%d ",v[i]-1);
    fclose(f2);
    return 0;
}