Cod sursa(job #1108704)

Utilizator vladradu2014Radu Vlad Alexandru vladradu2014 Data 16 februarie 2014 00:04:35
Problema Sortare topologica Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 2.28 kb
#include <stdio.h>
#include <malloc.h>
#include <string.h>

int *din;

struct node{
 int info;
 struct node* next;
};

struct queue{
    struct node *back;
    struct node *front;
    struct node *it;
    
    void (*push)(struct queue* q,int _info);
    int (*pop)(struct queue* q);
    int (*isEmpty)(struct queue* q);
    int (*size)(struct queue*q);
};

int _isEmpty(struct queue*q){
    return (q->front==NULL);
}

void _push(struct queue* q,int _info){
    struct node *n=(struct node*)malloc(sizeof(struct node));
    n->info=_info;
    if(q->front==NULL){
        q->front=q->back=n;
        q->it=q->front;
    }
    else{
        q->back->next=n;
        q->back=n;
    }
}

int _pop(struct queue *q){
    struct node *aux=q->front;
    q->front=q->front->next;
    int _info=aux->info;
    free(aux);
    return _info;
}

int _size(struct queue *q){
    if(q->back==NULL)
      return 0;
    return (q->back-q->front)/2+1;
}
void initQueue(struct queue *q){
    q->front=q->back=NULL;
    q->isEmpty=_isEmpty;
    q->push=_push;
    q->pop=_pop;
    q->size=_size;
}

struct node** graph(FILE *fp, int N,int M){
    int i;
    int X,Y;
    din=(int*)malloc(sizeof(int)*(N*2));
    struct node **G=(struct node**)malloc(sizeof(struct node*)*(N*2));
    for(i=0;i<M;i++){
        fscanf(fp,"%d%d",&X,&Y);
        din[Y]++;
        struct node *pawn1=(struct node *)malloc(sizeof(struct node));
        pawn1->info=Y;
        pawn1->next=*(G+X);
        *(G+X)=pawn1;
    }
    return G;
}




int main()
{
    FILE *fp;
    int N,M;
	int i;
    struct queue q;
    initQueue(&q);
    fp=fopen("sortaret.in","r");
    fscanf(fp,"%d%d",&N,&M);
	if(N==0 || M==0)
       return 1;
    struct node **G=graph(fp,N,M);
    fclose(fp);
    for(i=1;i<=N;i++){
         if(!din[i])
           q.push(&q,i);
    }
    for(i=1;i<=N;i++){
        int in=(q.it)->info;
        struct node*aux=G[in];
        while(aux){
            --din[aux->info];
            if(din[aux->info]==0)
              q.push(&q,aux->info);
             aux=aux->next;
        }
        q.it=q.it->next;
   }
   free(G);
   fp=fopen("sortaret.out","w");
   while(!q.isEmpty(&q))
    fprintf(fp,"%d ",q.pop(&q));
   fclose(fp);
   
   return 0;
}