Cod sursa(job #2544438)

Utilizator thinkphpAdrian Statescu thinkphp Data 12 februarie 2020 01:09:36
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.92 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;

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

typedef struct topsort Topsort;

void dfs(int node, int seen[], Node**adjList) {     

     seen[node] = 1;

     printf("%d ", node);

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

         if(!seen[c->data]) 

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

void execute(struct topsort *top) {
    
     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);
     	 }
     }
};

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);    
    
    //clean up
    for(int i = 1; i <= nodes; ++i) 

    	if(adjList[i]!=NULL) 

    	   free(adjList[i]);

	return 0;
}