Cod sursa(job #660939)

Utilizator blustudioPaul Herman blustudio Data 13 ianuarie 2012 15:12:20
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
/*
 * Autor: Paul Herman
 * Problema: sortare topologica
 * Data: 13.01.2012
 * Punctaj: -
 * Link: http://www.infoarena.ro/problema/sortaret
 */
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

bool vizitat[50000]; //Lista de vecini a fiecarui nod
vector<int> vecini[50000]; //Starea de vizitare a fiecarui nod
deque<int> coada;
int n; //Nr. de noduri
int m; //Nr. de muchii

inline void dfs(int nod)
{
	vizitat[nod] = true;
	for (int i = 0; i < vecini[nod].size(); i++)
		if (vizitat[vecini[nod][i]] == false)
			dfs(vecini[nod][i]);
	coada.push_front(nod);
}
inline void sortare_topologica()
{
	for (int i = 0; i < n; i++)
		if (vizitat[i] == false)
			dfs(i);
}
inline void scriere()
{
	ofstream fout("sortaret.out");
	for (int i = 0; i < n; i++)
		fout << coada[i] << ' ';
	fout.close();
}
inline void citire()
{
	int a, b; //Nodurile intre care vom avea muchie
	ifstream fin("sortaret.in");
	fin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		fin >> a >> b;
		vecini[a].push_back(b);
	}
	fin.close();
}
int main()
{
	citire();
	sortare_topologica();
	scriere();
	return 0;
}