Cod sursa(job #595482)

Utilizator balakraz94abcd efgh balakraz94 Data 12 iunie 2011 20:17:03
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
#include<vector>
#define infile "sortaret.in"
#define outfile "sortaret.out"
#define n_max 50000 
#define pb push_back
using namespace std;


vector < vector <int> > v(n_max,1);

vector <int> post(1);

bool uz[n_max];

int n,m,nr;


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&n,&m);
	
	int x,y;
	
	for(;m;m--)
	{
		scanf("%d %d",&x,&y);
		
		v[x].pb(y);
		v[x][0]++;
	}
	
	
	fclose(stdin);
}



void dfs(int nod)
{
	uz[nod]=1;
	
	for(int i=1;i<=v[nod][0];i++)
		if(!uz[v[nod][i]])
			dfs(v[nod][i]);
		
	post.pb(nod);
}



void rezolva()
{
	for(int i=1;i<=n;i++)
		if(!uz[i])
			dfs(i);
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	
	for(int i=n;i;i--)
		printf("%d ",post[i]);
	
	
	fclose(stdout);
}



int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}