Cod sursa(job #448708)

Utilizator lakat_tLakatos Tamas lakat_t Data 4 mai 2010 15:06:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<iostream>
#include<fstream>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct node
{
	int x;
	node *kov;
};

int n,m,x,y,latott[50001],w[50001],db;

node *v[50001];

int betesz()
{
	
	
	node *p;
	p = new node;
	p->x=y;
	p->kov=v[x];
	v[x]=p;
	return 0;
}

int topo(int cs)
{
	latott[cs]=1;
	node *p=v[cs];
	while(p!=NULL)
	{
		if(latott[p->x]==0)
			topo(p->x);
		p=p->kov;
	}
	w[db]=cs;
	db--;
	return 0;
}
int main()
{
	fin>>n>>m;
	db=n;
	for(int i=1;i<=m;i++)
	{
		fin>>x>>y;
		betesz();
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<i<<' ';
		node *p=v[i];
		while(p!=NULL)
		{
			cout<<p->x<<' ';
			p=p->kov;
		}
		cout<<'\n';
	}*/
	for(int i=1;i<=n;i++)
	{
		if(latott[i]==0)
			topo(i);
	}
	for(int i=1;i<=n;i++)
	{
		fout<<w[i]<<' ';
	}
	return 0;
}