Cod sursa(job #550635)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 9 martie 2011 20:12:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<vector>
using namespace std;

const int NMAX=50000;
int cnt=0,*mem,*viz;
vector<int> v[NMAX];
ofstream out("sortaret.out");

void dfs2(const int&, vector<int> *);

void dfs1(vector<int> *v, const int& noduri)
{
	for(int i=0;i<noduri;i++)
	{
		if(!viz[i])
			dfs2(i,v);
	}
	for(int i=cnt-1;i>=0;i--)
		out<<mem[i]+1<<" ";
	out<<endl;
	out.close();
}
	
void dfs2(const int& rad, vector<int> *v)
{
	viz[rad]=1;
	for(int i=0;i<(int) v[rad].size();i++)
	{
		if(!viz[v[rad][i]])
			dfs2(v[rad][i],v);;
	}
	mem[cnt++]=rad;
}

int main()
{
	ifstream in("sortaret.in");
	int n,m;
	in>>n>>m;

	mem=new int[n];
	viz=new int[n];
	int a,b;
	for(int i=0;i<m;i++)
	{
		in>>a>>b;
		--a;
		--b;
		v[a].push_back(b);
	}
	in.close();
	dfs1(v,n);
	delete[] mem;
	delete[] viz;
}