Cod sursa(job #1298105)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 22 decembrie 2014 15:45:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
#include <stack>

int main(){
	std::ifstream fin("sortaret.in");
	std::ofstream fout("sortaret.out");

	unsigned n,m;
	fin>>n>>m;

	std::vector< std::vector<unsigned> > Adj(n+1);
	std::vector<unsigned> gr(n+1,0);

	for(unsigned i=0;i<m;++i){
		unsigned a,b; fin>>a>>b;
		gr[b]++;
		Adj[a].push_back(b);
	}

	std::stack<unsigned> st;
	for(unsigned i=1;i<=n;++i)
		if(gr[i]==0) st.push(i);

	while(!st.empty()){
		unsigned v=st.top();
		fout<<v<<" ";
		st.pop();

		for(auto it=Adj[v].begin();it!=Adj[v].end();++it){
			gr[*it]--;
			if(gr[*it]==0) st.push(*it);
		}
	}
	fout<<'\n';
}