Cod sursa(job #345881)

Utilizator vladiiIonescu Vlad vladii Data 5 septembrie 2009 12:41:32
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <list>
#include <queue>
using namespace std;
int n, m, s, drum[1000010];
list<int>a[1000010];
void BF();
int main() {
    int x, y, i;
    FILE *in = fopen("bf.in", "r"), *out= fopen("bf.out", "w");
    fscanf(in, "%d%d%d", &n, &m, &s);
    for(i=1; i<=m; i++) {
             fscanf(in, "%d%d", &x, &y);
             a[x].push_back(y);
    }
    for(i=1; i<=n; i++) {
             drum[i]=-1;
    }
    BF();
    for(i=1; i<=n; i++) {
             fprintf(out, "%d ", drum[i]);
    }
    return 0;
}

void BF() {
    int p;
    queue<int>c;
    c.push(s); drum[s]=0;
    while(!c.empty()) {
         p=c.front();
         for(list<int>::iterator it=a[p].begin(); it!=a[p].end(); it++) {
                                 if(drum[*it]==-1) {
                                       drum[*it]=drum[p]+1;
                                       c.push(*it);
                                 }
         }
         c.pop();
    }
}