Cod sursa(job #698970)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 29 februarie 2012 17:01:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 50010
using namespace std;
vector<int>v[MAXN];
stack<int>S;
int n,m;
bool viz[MAXN];
void df(int x)
{
	viz[x]=1;
	for(int i=0;i<v[x].size();i++)
	if(!viz[v[x][i]]) df(v[x][i]);
	S.push(x);
}
int main()
{
	int x,y;
	ifstream fi("sortaret.in");
	ofstream fo("sortaret.out");
	fi>>n>>m;
	for(int i=1;i<=m;i++) 
	{
		fi>>x>>y;
		v[x].push_back(y);
	}
	for(int i=1;i<=n;i++) if(!viz[i]) df(i);
	while(!S.empty()) { fo<<S.top()<<" "; S.pop(); }
	return 0;
}