Cod sursa(job #919670)

Utilizator kitzTimofte Bogdan kitz Data 19 martie 2013 19:30:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
#include <queue>
#define Nm 50100
std::vector < int > A[Nm];
std::queue < int > Q;
std::ifstream f ("sortaret.in"); std::ofstream g("sortaret.out");
int n, m, d[Nm];
int main()
{
	f>>n>>m;
	int x, y;
	for(int i=1;i<=m;i++){ f>>x>>y; A[x].push_back(y); d[y]++; }
	for(int i=1;i<=n;i++) if(d[i]==0) Q.push(i);
	std::vector<int>::iterator it;
	while(!Q.empty()){
		x = Q.front(); g<<x<<" "; Q.pop();
		for(it = A[x].begin(); it != A[x].end(); ++it){
            d[*it]--;
            if(d[*it] == 0) Q.push(*it);
        }
	}
	g<<"\n"; g.close();
	return 0;
}