Cod sursa(job #387328)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 27 ianuarie 2010 12:52:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<vector>

#define pb push_back
#define N 50002

using namespace std;

vector<int> v[N], q;
int n, m , i, j, x, y, noduri[N], xx;

void rezolva();

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);
		v[y].pb(x);
		noduri[x]++;
	}
	rezolva();
	
	return 0;
}

void rezolva(){
	for (i = 1; i <= n; i++)
		if (noduri[i] == 0)
			q.pb(i);
	
	for (i = 0; i<q.size(); i++){
		xx = q[i];
		for (j = 0; j < v[xx].size(); j++){
			noduri[v[xx][j]]--;
			if (noduri[v[xx][j]] == 0)
				q.pb(v[xx][j]);
		}
	}
	
	for (i = q.size()-1; i >= 0; i--)
		printf("%d ", q[i]);
}