Cod sursa(job #486652)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 22 septembrie 2010 12:10:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
// infoarena: problema/sortaret //

#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>

#define MAXN 100010
#define MAXM 500010
using namespace std;

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

int i,j,n,m,a,b,gi[MAXN];
bool viz[MAXN];
vector<int> g[MAXN];
vector<int> sol;


const char* show(vector<int> container)
{
	if(container.empty())
		return "[]";
	stringstream s;
	s << "[ ";
	typeof(container.begin()) it=container.begin();
	s << *it;
	for(it++; it != container.end(); it++)
		s << ", " << *it;
	s << " ]";
	return s.str().c_str();
}

void dfs(int nod)
{
	if(nod == 4)
	{
		cerr << nod;
	}
	viz[nod] = true;
	for(int i=0; i<g[nod].size(); ++ i)
		if(!viz[g[nod][i]])
			dfs(g[nod][i]);
	sol.push_back(nod);
}

int main()
{
	in>>n>>m;
	
	for(i=1; i<=m; i++)
	{
		in>>a>>b;
		for(j=0; j<g[a].size(); ++j)
			if(g[a][j] == b)
				break;
		if(j != g[a].size())
			continue;
		
		++ gi[b];
		g[a].push_back(b);
	}
	
	for(i=1; i<=n; i++)
		if(gi[i] == 0)
			dfs(i);
		
	for(vector<int>::reverse_iterator it=sol.rbegin(); it!=sol.rend(); ++it)
		out<<*it<<' ';
		
	return 0;
}