Cod sursa(job #862121)

Utilizator ingridutz95Botescu Ingrid ingridutz95 Data 22 ianuarie 2013 11:33:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream>
#include<vector>
#define Nmax 50002
using namespace std;
int N,M,d[Nmax],Q[Nmax];
vector <int> G[Nmax];
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int main(){
	f>>N>>M;
	for(int a,b,i=1;i<=M;i++)
		f>>a>>b,G[a].push_back(b),d[b]++;
	for(int i=1;i<=N;i++)
		if(d[i]==0)Q[++Q[0]]=i;
	for(int i=1;i<=N;++i){
		int x=Q[i];
		vector <int>::iterator it=G[x].begin(),sf=G[x].end();
		for(;it!=sf;++it){
			d[*it]--;
			if(d[*it]==0) Q[++Q[0]]=*it;
		}
	}
	for(int i=1;i<=N;i++)
		g<<Q[i]<<" ";
	g.close();
	return 0;
}