Cod sursa(job #1035974)

Utilizator roby2001Sirius roby2001 Data 18 noiembrie 2013 21:53:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
/*
          ~Keep It Simple!~
*/




#include <stdio.h>
#include <list>

using namespace std;

list<int> graph[50001];
list<int> sorted;
int n,m;
int viz[50001];



void dfs(int k)
{
	if(viz[k] == 2)
		return;
	viz[k] = 1;
	sorted.push_back(k);
	for(list<int>::iterator it = graph[k].begin(); it!=graph[k].end(); it++)
		if(!viz[*it])
			dfs(*it);
	viz[k] = 2;
}

void solve()
{
	for(int i=1;i<=n;i++)
		if(!viz[i])
			dfs(i);
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
    
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		graph[x].push_back(y);
	}

	solve();

	for(list<int>::iterator it = sorted.begin(); it!=sorted.end(); it++)
		printf("%d ",*it);
}