Cod sursa(job #2206894)

Utilizator vic_d54Doroftei Victor vic_d54 Data 24 mai 2018 10:10:31
Problema BFS - Parcurgere in latime Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 5995 // NMAX==KMAX
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
// vector <int> a[NMAX+5];
int n,m,mu,x,y,nrc,k,p,q,c[NMAX+5],dist[NMAX+5];
bool viz[NMAX+5],a[NMAX+5][NMAX+5];
void reset()
{
    int i;
    for(i=1;i<=n;i++)
        viz[i]=0;
}
void bfs(int v)
{
    int inc,sf,i;
    inc=sf=1;
    viz[v]=1;
    c[1]=v;
    dist[v]=0;
    while(inc<=sf)
    {
        for(i=1;i<=n;i++)
            if(!viz[i] and a[c[inc]][i])
            {
                c[++sf]=i;
                viz[i]=1;
                dist[i]=dist[c[inc]]+1;
            }
        inc++;
    }
}
int main()
{
    int i;
    in>>n>>m>>p;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        a[x][y]=1; // ORIENTAT
    }
    bfs(p);
    for(i=1;i<=n;i++)
        if(i!=p and dist[i]==0)
            dist[i]=-1;
    for(i=1;i<=n;i++)
        out<<dist[i]<<' ';
    return 0;
}