Pagini recente » Cod sursa (job #1236334) | Cod sursa (job #1351587) | Cod sursa (job #2330571) | Cod sursa (job #358401) | Cod sursa (job #1460279)
#include <stdio.h>
#include <stdlib.h>
typedef struct Graf{
int n,m; // noduri muchii
int **matrix; // graf efectiv
}Graf ;
typedef struct Queue{
int val ;
struct Queue * next ;
}Queue ;
void init(Graf * g , int n){
g->n = n ;
g->matrix = (int**)malloc((n+1)*sizeof(int*));
int i ;
for (i = 0 ; i <= n ; i++)
g->matrix[i] = (int*)calloc((n+1),sizeof(int));
g->m = 0 ;
}
void add(Graf * g , int x , int y ){ // add doar pentru grafuri orientate
g->matrix[x][y] = 1 ;
g->m ++ ;
}
void print_graf(Graf g){
int i , j ;
for (i = 1 ; i <= g.n;i++){
printf("\n");
for(j = 1 ; j <= g.n ;j++)
printf("%d ",g.matrix[i][j] );
}
}
int grad_intern(Graf g ,int nod ){
int i ;
for ( i = 1 ; i <= g.n; i++)
if(g.matrix[nod][i] != 0 )
return 0 ;
return 1 ;
}
void add_queue(Queue ** front , Queue ** rear , int val){
if(*front == NULL){
*front = (Queue *)malloc(sizeof(Queue));
(*front)->val = val ;
(*front)->next = NULL ;
*rear = *front ;
return ;
}
Queue * nou = (Queue*)malloc(sizeof(Queue));
nou->val = val ;
nou->next = NULL ;
(*rear)->next = nou ;
*rear = nou ;
}
void ts(Graf g , int nod, int * vizitat,FILE * out){
vizitat[nod] = 1 ;
fprintf(out,"%d ",nod );
int i ;
for (i = g.n; i >= 0 ; i--)
if(g.matrix[i][nod] && !vizitat[i])
ts(g,i,vizitat,out);
}
int main(){
FILE * in = fopen("sortaret.in" , "r") ;
FILE * out = fopen("sortaret.out","w") ;
int N , M ;
Queue * front = NULL;
Queue * rear = NULL ;
fscanf(in,"%d %d",&N,&M);
Graf g ;
int * vizitat = (int*)calloc(N,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(grad_intern(g,i))
add_queue(&front,&rear,i);
Queue * cursor = front ;
while(cursor != NULL){
ts(g,cursor->val,vizitat,out);
cursor = cursor->next ;
}
fprintf(out,"\n" );
fclose(in);
fclose(out);
return 0 ;
}