Cod sursa(job #211454)

Utilizator vlad_popaVlad Popa vlad_popa Data 2 octombrie 2008 12:31:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 50005
#define pb push_back

int N, M;
int gr[MAXN];
int Q[MAXN];
vector<int> G[MAXN];

void read (){
	int a, b;
	for (scanf ("%d %d\n", &N, &M); M; -- M){
		scanf ("%d %d\n", &a, &b);
		G[a].pb(b);
		++ gr[b];
	}
}

void solve (){
	for (int i = 1; i <= N; ++ i)
		if (!gr[i]) Q[++Q[0]] = i;

	int nod, sz;
	for (int i = 1; i <= N; ++ i){
		nod = Q[i], sz = G[nod].size();
		//printf ("%d\n", nod);
		for (int j = 0; j < sz; ++ j)
		    (gr[G[nod][j]] - 1) ? -- gr[G[nod][j]] : (-- gr[G[nod][j]], Q[++Q[0]] = G[nod][j]); 		
	}

	for (int i = 1; i <= N; ++ i) printf ("%d ", Q[i]);
	printf ("\n");
}
																							   

int main (){
	freopen ("sortaret.in", "r", stdin);
	freopen ("sortaret.out", "w", stdout);

    read ();
	solve ();

	return 0;
}