Cod sursa(job #761657)

Utilizator VladberilaVladutz Vladberila Data 26 iunie 2012 21:56:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
using namespace std;
FILE *f = fopen("sortaret.in","r");
FILE *g = fopen("sortaret.out","w");
int n,m,Q[50001],grad[50001],i;
vector<int> G[50001];

void read(){
	
	fscanf(f,"%d%d",&n,&m);
	for(i = 0;i<m;i++){
		
		int x,y;
		fscanf(f,"%d%d",&x,&y);
		grad[y]++;
		G[x].push_back(y);
	}
}

void write(){
	
	for(i = 1;i<=n;i++)
		fprintf(g,"%d ",Q[i]);
}

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

int main(){
	
	read();
	solve();
	write();
	return 0;
}