Cod sursa(job #252912)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 5 februarie 2009 01:04:20
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.53 kb
#include<stdio.h>
#define infile "sortaret.in"
#define outfile "sortaret.out"
#define nmax (50*1000+1)
#define mmax (100*1000+1)
struct lista
	{
	int n,p; //nod si pozitie
	} l[mmax];
int p[nmax]; //pozitia din lista
int post[nmax]; //vectorul de psotordine al parcurgerii DFS
char viz[nmax]; //v[i]=1 daca a fost vizitat nodul i
int n; //numarul de noduri

//adauga arcul (x,y)
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
	{
	l[m].n=y; l[m].p=p[x]; p[x]=m;
	}

void citire(struct lista l[mmax], int p[nmax], int *n)
	{
	int i,m,x,y;
	scanf("%d %d\n",n,&m);
	for(i=1;i<=m;i++)
		{
		scanf("%d %d\n",&x,&y); //citim arcul
		add(l,p,i,x,y); //adaugam arcul in lista
		}
	}

void dfs(struct lista l[mmax], int p[nmax], int post[nmax], char viz[nmax], int n) //n - nodul din care facem parcurgerea
	{
	int ul=p[n];
	while(ul) //cat timp n are copii
		{
		if(!viz[l[ul].n]) //daca fiul nu a fost vizitat
			dfs(l,p,post,viz,l[ul].n); //parcurg fiul
		ul=l[ul].p; //copilul urmator al lui n
		}
	post[++post[0]]=n; //marcam in vectorul de postordine ca am terminat de vizitat toti vecinii
	}

int main()
{
int i;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(l,p,&n); //citim datele din fisier si construim lista
for(i=1;i<=n;i++)
	if(!viz[i]) //daca nodul nu a fost vizitat (vom avea o alta componenta conexa)
		dfs(l,p,post,viz,i);

for(i=n;i>0;i--) //parcurgem si afisem vectorul de psotordine de la coada
	printf("%d ",post[i]);

fclose(stdin);
fclose(stdout);
return 0;
}