Cod sursa(job #776529)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 9 august 2012 22:12:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#include<vector>
#define NMAX 50010

using namespace std;

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

vector<int> a[NMAX];
int n, m, ord[NMAX], vz[NMAX], nr[NMAX];

void Citeste()
{
	int i, x, y;
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y;
		a[x].push_back(y); ++nr[x];
	}
}

void DFS(int nod)
{
	int i, f;
	vz[nod]=1;
	for (i=0; i<nr[nod]; ++i)
	{
		f=a[nod][i];
		if (!vz[f]) DFS(f);
	}
	ord[++ord[0]]=nod;
}

void Solve()
{
	int nod;
	for (nod=1; nod<=n; ++nod)
		if (!vz[nod]) DFS(nod);
}

void Scrie()
{
	int i;
	for (i=n; i>0; --i) g<<ord[i]<<" ";
}

int main()
{
	Citeste();
	Solve();
	Scrie();
	f.close();
	g.close();
	return 0;
}