Cod sursa(job #1234471)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 27 septembrie 2014 14:20:19
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<iostream>
#include<queue>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");

queue<int> cda;
struct lista{
    int i;
    lista *urm;
};

struct lista *v[100005];
int coada[200005],cap=1,spate=0,n,m,s;
int sol[100005],viz[100005];

void adauga(int x,int y)
{

    lista *nou;
    nou = new lista;
    nou->i = y;
    nou->urm = v[x];
    v[x] = nou;
}

void citire()
{

    in>>n>>m>>s;
    int x,y;
    for(int j = 1 ; j <= m ; j++)
    {

        in>>x>>y;
        adauga(x,y);
    }
    in.close();
}

void parcurge(int start)
{

    cda.push(start);
    viz[start] = 1;
    sol[start] = 0;
    int k;
    lista *it;
    while(!cda.empty())
    {

        k = cda.front();
        viz[k] = 1;
        for( it = v[k] ; it ; it = it->urm)
            if(sol[it->i] == -1){
                cout<<it->i<<"\n";
                sol[it->i] = sol[k] + 1;
                cda.push(it->i);
            }
        cda.pop();
    }
}

void init()
{

    for(int i = 1 ; i <= n ; i++)
        sol[i] = -1;
}

int main()
{

    citire();
    init();
    parcurge(s);
    for(int i = 1 ; i <= n ; i++)
        out<<sol[i]<<" ";
    out.close();
    return 0;
}