Cod sursa(job #2594848)

Utilizator mrsdumbMaria Timbur mrsdumb Data 6 aprilie 2020 18:16:35
Problema BFS - Parcurgere in latime Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.47 kb

#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct{
    int culoare;
    int *vec;
    int m;
}Node;



typedef struct{
    int s, d;
}Arc;



#define alb 0
#define gri 1
#define negru 2



int *S, vf;
Node *v;



void dfs(int i){

    int k;
    v[i].culoare = gri;
    for(int j = v[i].m ; j--; ){
        k = v[i].vec[j];
        if(v[k].culoare == alb)
        dfs(k);
    }
    S[vf++] = i;
    v[i].culoare = negru;
}



int main(){
    FILE *f_in = fopen("sortaret.in", "r");
    FILE *f_out = fopen("sortaret.out", "w");
    Arc *a;
    int n, m, i, j;
    scanf("%d%d", &n, &m);
    n++;
    v = (Node*)malloc( sizeof(*v) * n );
    a = (Arc*)malloc( sizeof(*a) * m );
    int *laf, *la;
    laf = la = (int*)malloc( sizeof(int) * m );
    S = (int*)malloc( sizeof(int) * n );
    for( i = 0; i < n; i++){
        v[i].culoare = alb;
        v[i].m = 0;
    }

    for( i = 0; i < m; i++){
        scanf("%d%d", &a[i].s, &a[i].d);
        v[a[i].s].m++;
    }


    for( i = 0; i < n; i++){
        v[i].vec = la;
        la += v[i].m;
        v[i].m = 0;
    }
    for( i = 0; i < m; i++){
        for( j = 0; j < v[a[i].s].m; j++)
        if(v[a[i].s].vec[j] == a[i].d)
        continue;
        v[a[i].s].vec[v[a[i].s].m++] = a[i].d;
    }

    vf = 0;
    for( i = 1; i < n; i++){
        if(v[i].culoare == alb){
        dfs(i);
    }
}

    for( i = vf; i--; )
    printf("%d ", S[i]);
    free(a);
    free(v);
    fclose(f_in);
    fclose(f_out);
    return 0;

}