Cod sursa(job #228490)

Utilizator FlorianFlorian Marcu Florian Data 7 decembrie 2008 13:19:14
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#define Max 100002
FILE*f=fopen("bfs.in","r");
FILE*g=fopen("bfs.out","w");
struct Nod
 {
 int info;
 Nod *urm;
 };
Nod *prim[Max];
int n;
int d[Max];
void insert(int x, int y) //nod de la x la y
 {
 Nod *p;
 p=new Nod;
 p->info=y;
 p->urm=prim[x];
 prim[x]=p;
 }
void bfs(int S)
 {
 int c[Max];
 int p=0,u=0;
 int i;
 for(i=1;i<=n;++i) d[i]=-1;
 d[S]=0;
 Nod *q;
 int x;
 c[0]=S;
 while(p<=u)
  {
  int x=c[p++];
  for(q=prim[x];q;q=q->urm)
   {
   if(d[q->info]==-1)
    {
    d[q->info]=d[x]+1;
    c[++u]=q->info;
    }
   }
  }
 for(i=1;i<=n;++i) fprintf(g,"%d ",d[i]);
 }
int main()
 {
 int m,s,i,x,y;
 fscanf(f,"%d%d%d",&n,&m,&s);
 while(m--)
  {
  fscanf(f,"%d%d",&x,&y);
  insert(x,y);
  }
 bfs(s);
 return 0;
 }