Cod sursa(job #969055)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 3 iulie 2013 13:42:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<vector>
using namespace std;
const int MAXN=50010;

int n,m,s[MAXN],vf=-1;
vector<int> g[MAXN];
bool visited[MAXN];


void citire()
{
	int x,y;
	ifstream fin("sortaret.in");
	fin>>n>>m;
	for (int k=1;k<=m;++k)
	{
		fin>>x>>y;
		g[x].push_back(y);
	}
	fin.close();
}
void dfs_visit(int v)
{
	for (vector<int>::iterator i=g[v].begin();i!=g[v].end();++i)
	{
		if (!visited[*i])
		{
			visited[*i]=true;
			dfs_visit(*i);
		}
	}
	s[++vf]=v;
}
void dfs()
{
	for (int i=1;i<=n;++i)
	{
		if (!visited[i])
		{
			visited[i]=true;
			dfs_visit(i);
		}
	}
}
void afisare()
{
	ofstream fout("sortaret.out");
	for (int i=vf;i>=0;--i)
		fout<<s[i]<<' ';
	fout<<'\n';
	fout.close();
}

int main()
{
	citire();
	dfs();
	afisare();
	return 0;
}