Cod sursa(job #473942)

Utilizator robigiirimias robert robigi Data 1 august 2010 20:08:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
// SortareTopologica.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("sortaret.in", "r");
FILE *g=fopen("sortaret.out", "w");

typedef struct nod
{
	int x;
	struct nod *adr;
};

nod *l[50001];

int postordine[50001], viz[50001];
int n, m, nr;


void add(int x, int y)
{
	nod *p=new nod;
	p->x=y;
	p->adr=l[x];
	l[x]=p;
}

void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		add(x, y);
	}
}


void dfs(int i)
{
	viz[i]=1;
	nod *p=l[i];
	while (p!=NULL)
	{
		if (!viz[p->x])
			dfs(p->x);
		p=p->adr;
	}
	postordine[++nr]=i;;
}



void program()
{
	for (int i=1; i<=n; ++i)
		if (!viz[i])
			dfs(i);
	for (int j=nr; j>0; --j)
		fprintf(g, "%d ", postordine[j]);
	for (int k=1; k<=n; ++k)
		if (!viz[k])
			fprintf(g, "%d ", k);
}


int main()
{
	read();
	program();
	return 0;
}