Cod sursa(job #412106)

Utilizator b_polarAgape Mihai b_polar Data 5 martie 2010 12:49:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <stack>
#define NMAX 50005
#define infile "sortaret.in"
#define outfile "sortaret.out"
using namespace std;

typedef struct nod{int x;nod *nxt;}*L;
L G[NMAX];
void add(int,int),citire(),rezolvare(),afisare();
int N,M;
short int aresef[NMAX],vizitat[NMAX];
stack<int> stiva;


int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	citire();
	rezolvare();
	afisare();
}

void afisare()
{
	while(!stiva.empty())
		printf("%d ",stiva.top()),stiva.pop();
}

void df(int n)
{
	vizitat[n]=1;
	for(L p=G[n];p;p=p->nxt)
		if(!vizitat[p->x])df(p->x);
	stiva.push(n);
}

void rezolvare()
{
	int i;
	for(i=1;i<=N;i++)
		if(!aresef[i])df(i);
}

void citire()
{
	int s,d;
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++)
		{
		scanf("%d %d",&s,&d);
		add(s,d);
		aresef[d]=1;
		}
}

void add(int s,int d)
{
	L a=new nod;
	a->x=d;
	a->nxt=G[s];
	G[s]=a;
}