Pagini recente » Borderou de evaluare (job #463098) | Cod sursa (job #1364771)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f1("bfs.in");
ofstream f2("bfs.out");
#define N 100*1002
struct nod
{
int val, next;
};
class coada
{
int k;
int c[N];
public:
coada();
void add(int x);
int extract();
bool empty() {return !k;};
};
class vect_liste
{
int nr, iter, poz;
int first[N], last[N];
nod L[N];
public:
vect_liste();
void add( int x, int val );
void set_iter(int x); // ca sa pot afla numerele din lista x
int give_next();
};
class graf
{
int n,m, s;
int dist[N];
vect_liste VL;
public:
graf();
void read();
void BFS();
void print_dist();
};
// ------------------------------------- coada -------------------------------------------
coada::coada()
{
k=0;
memset(c, 0, sizeof(c));
}
void coada::add(int x)
{
c[++k]= x;
}
int coada::extract()
{
return c[k--];
}
// ---------------------------------------- vect_liste -----------------------------
vect_liste::vect_liste()
{
nr=0;
memset(first, 0, sizeof(first) );
memset(last, 0, sizeof(last));
}
void vect_liste::add( int x, int val )
{
L[++nr].val= val;
L[last[x] ].next = nr;
last[x]=nr;
if (!first[x] )
first[x]=nr;
}
void vect_liste::set_iter(int x)
{
poz=first[x];
iter=x;
}
int vect_liste::give_next()
{
int p1= poz;
poz= L[poz].next;
return L[p1].val;
}
// --------------- graf -----------------------------------
graf::graf()
{
memset(dist, -1, sizeof(dist));
VL= vect_liste();
}
void graf::read()
{
f1>>n>>m>>s;
int i,x,y;
for (i=1; i<=m; i++)
{
f1>>x>>y;
VL.add(x,y);
}
}
void graf::BFS()
{
int x, v, pas=0;
coada c1, c2;
c1.add(s);
while (!c1.empty() )
{
while (!c1.empty())
{
x= c1.extract();
VL.set_iter(x); // setez iteratorul pe x ca sa vad vecinii lui
v= VL.give_next();
while ( v )
{
if ( dist[v] == -1 )
{
c2.add( v );
dist[v]= pas+1;
}
v= VL.give_next();
}
}
while (!c2.empty())
c1.add( c2.extract() );
pas++;
}
dist[s]=0;
}
void graf::print_dist()
{
for (int i=1; i<=n; i++)
f2<<dist[i]<<" ";
}
int main()
{
graf g;
g.read();
g.BFS();
g.print_dist();
f2.close();
return 0;
}