Cod sursa(job #1422949)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 20 aprilie 2015 14:52:43
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>

using namespace std;

fstream in("bfs.in",ios::in);
fstream out("bfs.out",ios::out);

#define nmax 100005

struct nod
    {
        int info;
        nod *next;
    }*lista[nmax]={};

void memorare(nod**);
void indexare(nod**,int*,int,int*);

int main()
{
    nod *p;
    int n,m,s,i,j,start[nmax]={},coada[nmax];

    in>>n>>m>>s;
    memorare(lista);
    indexare(lista,start,s,coada);

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













/*
    for(i=1;i<=n;i++)
    {
        cout<<i<<"- ";
        p=lista[i];
        while(p)
        {
            cout<<p->info<<" ";
            p=p->next;
        }
        cout<<"\n";
    }
*/



    return 0;
}

void memorare(nod *lista[nmax])
{
    nod *p;
    int i,j;

    while(in>>i>>j)
    {
        p=new nod;
        p->info=j;
        p->next=lista[i];
        lista[i]=p;
    }

}

void indexare(nod *lista[nmax],int start[nmax],int s,int coada[nmax])
{
    nod *p;
    int ic=1,sf=1;
    coada[ic]=s;
    while(ic<=sf)
    {
        p=lista[coada[ic]];
        while(p)
        {
            if(p->info!=s&&start[p->info]==0)
            {
                sf++;
                coada[sf]=p->info;
                start[p->info]=start[coada[ic]]+1;
            }
            p=p->next;
        }
        ic++;
    }

}