Cod sursa(job #407857)

Utilizator xtephanFodor Stefan xtephan Data 2 martie 2010 18:06:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<vector>


using namespace std;

long n,m,grad[50010];
vector<int> Graf[50010];
vector<int> Q;
//long Q[50010];

void cit();
void rez();
void afis();


int main() {
	
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}


void cit() {
	
	scanf("%ld%ld",&n,&m);
	
	for(long i=1; i<=m; i++) {
		long x,y;
		scanf("%ld%ld",&x,&y);
		Graf[x].push_back(y);
		grad[y]++;
	}
}


void rez() {
	
	long i;
	vector<int>::iterator it;
	
	Q.push_back(0);
	
	for(i=1; i<=n;i++)
		if(grad[i] == 0)
			//Q[++Q[0]]=i;
			Q.push_back(i);
		
	for(i=1; i<=n;i++) {
		
		long x = Q[i];
		
		for( it=Graf[x].begin(); it!=Graf[x].end(); ++it) {
			
			grad[*it]--;
			
			if(grad[*it] == 0)
				//Q[++Q[0]]=*it;
				Q.push_back(*it);
		}
		
	}
}


void afis() {
	for(long i=1; i<=n;i++)
		printf("%ld ",Q[i]);
}