Cod sursa(job #1988465)

Utilizator b10nd3Oana Mancu b10nd3 Data 3 iunie 2017 03:28:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>

using namespace std;

int main(){
ifstream in; ofstream out;
in.open("sortaret.in"); out.open("sortaret.out");
out.clear();

//vars
int m,n;
in>>n>>m;
int a,b, i, sorted[n+1], gradExt[n+1];
vector<int> aux[n+1]; vector<int>::iterator it;
sorted[0]=0;
for(i=1;i<=n;i++) gradExt[i]=0;

//reading and storing data
for(i=1;i<=m;i++){
   in>>a>>b;
   gradExt[b]++;
   aux[a].push_back(b); 
}

//magic
for(i=1;i<=n;i++)
   if(gradExt[i]==0) sorted[++sorted[0]]=i;
for(i=1;i<=n;i++){
   a=sorted[i];
   for(it=aux[a].begin();it!=aux[a].end();++it){
       gradExt[*it]--;
       if(gradExt[*it]==0) sorted[++sorted[0]]=*it;
   }
}

//print solution
for(i=1;i<=n;i++) out<<sorted[i]<<" ";

return 0;}