Cod sursa(job #2536561)

Utilizator thinkphpAdrian Statescu thinkphp Data 2 februarie 2020 11:45:28
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>
#include <malloc.h>
#include <memory.h>
#define FIN  "sortaret.in"
#define FOUT "sortaret.out"
#define SIZE 100100

struct TNode {

	   int data;
	   struct TNode *next;
};

typedef struct TNode Node;

Node *list[ SIZE ];

int sol[ SIZE ], 
    seen[ SIZE + 1 ], 
    stack[ SIZE + 1 ];

void addEdge(int x, int y){

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

	       c->data = y;

	       c->next = list[x];

	       list[x] = c;
}

void dfs(int nodes, int node) {

	 int top = 0, found;

	 Node *curr, *c, *p;	 

	 seen[ node ] = 1;

	 stack[ top ] = node; 

     sol[++sol[0]] = node;

     while(top >= 0) {

          curr = list[stack[top]];

          found = 0;

          for(c = curr; !found && c != NULL; c = c->next) {

                    if(!seen[c->data]) {

                    	found = 1;

                    	p = c;
                    }
          }

          if(found) {

             seen[p->data] = 1;

             stack[++top] = p->data;

             sol[++sol[0]] = p->data;

          } else top--;
	 }

}

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);

    while(edges--) {
 
         scanf("%d %d", &x, &y); 

         addEdge(x,y);
    } 

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

    for(int i = 1; i <= nodes; ++i)

    if(!seen[i]) dfs(nodes, i);
    
    for(int i = 1; i <= nodes; ++i) printf("%d ", sol[i]);
    
	return 0;
}