Cod sursa(job #341772)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 19 august 2009 15:33:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(c) (int)((c).size())
#define f first
#define s second

#define fin  "sortaret.in"
#define fout "sortaret.out"

#define NMAX 50010

int N, M;
vector<int> g[NMAX];
char viz[NMAX];
stack<int> st;

void ReadData()
{
	int a, b;

	ifstream f(fin);

	f >> N >> M;
	for ( int i = 1; i <= M; ++i )
		f >> a >> b, g[a].pb(b);
	f.close();
}

void df(int x)
{
	viz[x] = 1;
	for ( int i = 0; i < sz(g[x]); ++i )
		if ( !viz[ g[x][i] ] )
			df( g[x][i] );
	st.push(x);
}

void Solve()
{
	memset(viz,0,sizeof(viz));
	for ( int i = 1; i <= N; ++i )
		if ( !viz[i] ) df(i);	
}

void PrintSol()
{
	ofstream f(fout);

	while ( !st.empty() )
	{
		f << st.top() << " ";
		st.pop();
	}

	f.close();
}

int main()
{
	ReadData();
	Solve();
	PrintSol();
	return 0;
}