Cod sursa(job #408052)

Utilizator me_andyAvramescu Andrei me_andy Data 2 martie 2010 20:18:06
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream.h>
#define max 100010

 ifstream f("bfs.in");
 ofstream g("bfs.out");
 long s,x,y,uz[max],vec[max],n,m,cost[max],i,j;

typedef struct nod
{
 int info;
 nod *urm;
}*pNod;

pNod a[max];

void add(pNod &prim,int inf)
{
 pNod x=new nod
 x->info=inf;
 x->urm=prim;
 prim=x;
}


int main()
{
 f>>n;
 f>>m;
 f>>s;
 for(i=1;i<=m;i++)
 {
 f>>x>>y;
 add(a[x],y);

 }



 vec[1]=s;
 uz[vec[1]]=1;
 j=1;
 for(i=1;i<=j;i++)
 {
   pNod prim=a[vec[i]];
  while(prim)
  {
   if(uz[prim->info]==0)
  { uz[prim->info]=1;
   cost[prim->info]=cost[vec[i]]+1;
   vec[++j]=prim->info;
   }
   prim=prim->urm;
  }
 }

 for(i=1;i<=n;i++)
 {
  if(cost[i]==0&&i!=s)
  g<<-1<<" ";
  else g<<cost[i]<<" ";

 }
 return 0;
}