Cod sursa(job #1341709)

Utilizator afkidStancioiu Nicu Razvan afkid Data 13 februarie 2015 00:28:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 50010


using namespace std;
vector<int> arcs[NMAX];
int visited[NMAX];
int n,m;


void Read()
{
	freopen("sortaret.in","r",stdin);
	int a,b;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;++i)
	{
		scanf("%d %d",&a,&b);
		arcs[a].push_back(b);
	}
}

stack<int> lifo;

void TopologicalSortUtil(int node)
{
	visited[node]=1;
	vector<int>::iterator it;
	for(it=arcs[node].begin();it!=arcs[node].end();++it)
	{
		if(!visited[*it])
		{
			TopologicalSortUtil(*it);
		}
	}
	lifo.push(node);
}

void TopologicalSort()
{
	for(int i=1;i<=n;++i)
	{
		visited[i]=0;
	}
	for(int i=1;i<=n;++i)
	{
		if(!visited[i])
		{
			TopologicalSortUtil(i);
		}
	}
}

void Write()
{
	freopen("sortaret.out","w",stdout);
	while(!lifo.empty())
	{
		printf("%d ",lifo.top());
		lifo.pop();
	}
	printf("\n");
}


int main()
{
	Read();
	TopologicalSort();
	Write();
	return 0;
}