Cod sursa(job #748940)

Utilizator stanescu_teodorStanescu Teodor stanescu_teodor Data 15 mai 2012 10:44:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#define pb push_back
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;

vector <int> g1[200000];
vector <int> :: iterator it;
int n,m,i,x,y,nc,D[100000],nr;
bool sel[200000];
ifstream f ("sortaret.in");
ofstream g ("sortaret.out");

void dfs (int x)
{
	vector <int> :: iterator it;
	sel[x]=true;
	for (it=g1[x].begin(); it!=g1[x].end(); it++)
		if (!sel[*it])
		{
			sel[*it]=true;
			dfs(*it);
		}
	D[++nr]=x;
}

int main ()
{
	f >>n>>m;
	for (i=1; i<=m; i++)
	{
		f>>x>>y;
		g1[x].pb(y);
	}
	nc=0;
	for (i=1; i<=n; i++)
		if (!sel[i]) 
		{
			nc++;
			dfs(i);
		}
		for (i=1; i<=nr; i++)
	g<<D[nr-i+1]<<' ';
	f.close();
	g.close();
}