Cod sursa(job #501567)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 15 noiembrie 2010 19:39:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>

#define pb push_back 
 
using namespace std;
vector <int> a[50001],v;
vector <int> :: iterator it;
int n,m,i,j,x,y;
bool ap[50001];

void Df(int x) {
	vector <int> :: iterator it;
	ap[x]=true;
	for (it=a[x].begin(); it!=a[x].end(); it++) 
		if (!ap[*it]) Df(*it);
	v.pb(x);
}

int main () {
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; i++) {
		scanf("%d%d",&x,&y);
		a[x].pb(y);
	}
	memset(ap,false,sizeof(ap));
	for (i=1; i<=n; i++) 
		if (!ap[i]) Df(i);
	reverse(v.begin(),v.end());
	for (it=v.begin(); it!=v.end(); it++)
		printf("%d ",*it);
	printf("\n");
	return 0;
}