Pagini recente » Cod sursa (job #2175793) | Cod sursa (job #1104158) | Cod sursa (job #1938601) | Cod sursa (job #2414617) | Cod sursa (job #1108704)
#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;
}