Cod sursa(job #1720419)

Utilizator ArkinyStoica Alex Arkiny Data 22 iunie 2016 14:58:59
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<stdlib.h>

struct Node
{
	int data;
	struct Node *next;
}*A[50010];


int viz[50010];

typedef struct Node Node;

Node *stk;


void push_list(Node **v, int data)
{
	Node *p = (Node*)malloc(sizeof(Node));
	p->data = data;
	p->next = *v;
	*v = p;
}


void dfs(int x)
{
	Node *p = A[x];
	viz[x] = 1;

	while (p)
	{
		if (!viz[p->data])
			dfs(p->data);
		p = p->next;
	}

	push_list(&stk, x);
   

}


FILE *in, *out;


int main()
{

	int N, M, x, y, i;


	in = fopen("sortaret.in", "r");
	out = fopen("sortaret.out", "w");

	fscanf(in, "%d%d", &N, &M);

	for (i = 1;i <= M;++i)
	{
		fscanf(in, "%d%d", &x, &y);

		push_list(&A[x], y);

	}

	for (int i = 1;i <= N;++i)
	{
		if (!viz[i])
		{
			dfs(i);
		}
	}

	Node *e = stk;

	while (e)
	{
		fprintf(out, "%d ", e->data);

		e = e->next;
	}

	return 0;
}