Cod sursa(job #1018433)

Utilizator taigi100Cazacu Robert taigi100 Data 29 octombrie 2013 16:20:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
/*
          ~Keep It Simple!~
*/
#include<stdio.h>
#include<list>
using namespace std;

int n,m;
list<int> Noduri[50001];
list<int> final;
int viz[50001];

void Df(int x)
{
	viz[x] = 1;
	for(list<int>::iterator it = Noduri[x].begin(); it != Noduri[x].end(); it++)
		if( viz[*it] == 0)
			Df(*it);
	viz[x] = 2;
	final.push_back(x);
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);

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

	for(int i=1;i<=n;i++)
		if(viz[i] == 0)
			Df(i);
	int nr=n;
	for(list<int>::iterator it = final.begin(); it != final.end(); it++)
	    viz[nr--]=*it;
	for(int i=1;i<=n;i++)
		printf("%d ",viz[i]);

	return 0;
}