Pagini recente » Cod sursa (job #2694748) | Cod sursa (job #1712341) | Cod sursa (job #1242362) | Cod sursa (job #3262104) | Cod sursa (job #1460313)
#include <stdio.h>
#include <stdlib.h>
typedef struct Stack{
int val ;
struct Stack * next ;
}Stack ;
typedef struct graf{
Stack **a; // matricea de adiacenta
int n,m ; //n noduri , m muchii /arce
}Graf ;
Stack * push(Stack * s,int val){
Stack * nou = (Stack*)malloc(sizeof(Stack));
nou->val = val ;
nou->next = s;
s = nou ;
return s ;
}
int * vazut = NULL ;
// stiva se foloseşte în două funcţii
// sortare topologică pornind dintr-un nod v
void ts (Graf g, int v,Stack ** s) {
vazut[v] = 1;
Stack * cursor = g.a[v];
while(cursor != NULL){
if(!vazut[cursor->val])
ts(g, cursor->val,s);
cursor = cursor->next ;
}
*s = push(*s, v);
}
void init(Graf * g,int n ){
g->n = n ;
g->m = 0 ;
g->a=(Stack**)calloc((n+1),sizeof(Stack*));
}
void add(Graf * g , int x , int y){//ATENTIE adauga arcuri , nu muchii
g->m ++ ; // marcam faptul ca a fost adaugat un arc
g->a[x]=push(g->a[x],y);
}
void print_stack(Stack * s,FILE * out){
Stack * cursor = s ;
while(cursor != NULL){
fprintf(out,"%d ",cursor->val );
cursor = cursor->next ;
}
}
int main(){
FILE * in = fopen("sortaret.in" , "r") ;
FILE * out = fopen("sortaret.out","w") ;
int N , M ;
fscanf(in , "%d %d",&N,&M);
Graf g ;
Stack * s = NULL ;
vazut = (int*)calloc((N+1),sizeof(int));
init(&g,N);
int i ;
int x , y ;
for( i = 1 ; i <= M ; i++){
fscanf(in,"%d %d",&x,&y);
add(&g,x,y);
}
for (i = 1; i <= N; i++)
if (vazut[i] == 0)
ts(g, i,&s);
print_stack(s,out);
fclose(in);
fclose(out);
return 0 ;
}