Cod sursa(job #918069)

Utilizator taigi100Cazacu Robert taigi100 Data 18 martie 2013 16:41:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<vector>
#include<list>
using namespace std;

#define max 100002

int nrd,nrn,grad[max];
list<int> solved[max];
bool visited[max];

void Visit(int node)
{
	list<int>::iterator it;
	for(it=solved[node].begin(); it!=solved[node].end(); it++)
		if( !visited[*it] )
			Visit(*it);
	visited[node]=1;
    solved[0].push_front(node);
}
void Solve(void)
{
	for(int i=1; i<=nrn; i++)
		if( !visited[i] )
			Visit(i);
}

void Read_Data(void)
{
	scanf("%d %d",&nrn,&nrd);

	int x,y;

	for(int i=1; i<=nrd; i++)
	{
		scanf("%d %d",&x,&y);
		solved[x].push_back(y);
		grad[x]++;
	}
}

void Print_Resault()
{
	for(list<int>::iterator i=solved[0].begin(); i!=solved[0].end(); i++)
		printf("%d ",*i);
}
int main(void)
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);

	Read_Data();
	Solve();
	Print_Resault();

	return 0;
}