Cod sursa(job #2544489)

Utilizator thinkphpAdrian Statescu thinkphp Data 12 februarie 2020 09:49:36
Problema Sortare topologica Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define SIZE 50010

struct TNode {
	   int data;
	   struct TNode *next;
};

typedef struct TNode Node;

Node* head=NULL;

struct topsort {	   
       int nodes;
       int edges;
       void (*addEdge)(struct topsort*);        
       Node **adjList;
};

typedef struct topsort Topsort;

void dfs(int node, int seen[], Node**adjList, int *ret) {     
     
     seen[node] = 1;     

     for(Node *c = adjList[node]; c; c = c->next)

         if(!seen[c->data]) 

         	dfs(c->data, seen, adjList, ret);                  


   Node *c = (Node*)malloc(sizeof(Node));

        	  c->data = node;

        	  c->next = head;

        	  head = c;        	       
}

void execute(struct topsort *top) {
    
     int *ret = (int*)malloc(sizeof(int));     

     int seen[top->nodes + 1];

     memset(seen, 0, sizeof(seen));

     for(int i = 1; i <= top->nodes; ++i) {

     	 if(!seen[i]) {
            
            dfs(i, seen, top->adjList, ret);
     	 }
     }     
};

//for debug
void display(Node**adjList, int nodes) {

	    for(int i = 1; i <= nodes; ++i) {
        
        if(adjList[i]!=NULL) {

        	   Node *curr = adjList[i];

               while(curr!=NULL) {

               	 printf("%d ", curr->data);

               	 curr = curr->next;
               }
        }

        printf("\n");
    }            

}

int main(int argc, char const *argv[])
{   

	int nodes, edges, x, y;
    
    freopen(FIN, "r", stdin);    
    freopen(FOUT, "w", stdout);    

    scanf("%d %d", &nodes, &edges);

    Node *adjList[nodes + 1];

    for(int i = 1; i <= nodes; ++i) adjList[i] = NULL;

    for(int i = 1; i <= edges; ++i) {

        scanf("%d %d", &x, &y);

        Node *c = (Node*)malloc(sizeof(Node));

        	  c->data = y;

        	  c->next = adjList[x];

        	  adjList[x] = c;        	  
    }
                                    
    Topsort top = {nodes, edges, execute, adjList}; 

    top.addEdge(&top);    

    while(head) {

    	printf("%d ", head->data); head = head->next;
    }
    
    //clean up
    for(int i = 1; i <= nodes; ++i) 

    	if(adjList[i]!=NULL) 

    	   free(adjList[i]);

	return 0;
}