Cod sursa(job #636811)

Utilizator danieladDianu Daniela danielad Data 19 noiembrie 2011 23:58:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector <int> v[50001];
int n,m,grad[50001],s[50001],nr=0;
void citire(int &n){
  f>>n>>m;
  for(int i=1;i<=n;i++)
  grad[i]=0;
  int x,y;
  for(int i=1;i<=m;i++){
    f>>x>>y;
    v[x].push_back(y);
    grad[y]++;
  }
}
void top(){
  int x;
  for(int i=1;i<=n;i++)
  if(grad[i]==0){
    nr++;
    s[nr]=i;
  }
  for(int i=1;i<=n;i++){
    x=s[i];
    for(int j=0;j<v[x].size();j++){
      grad[v[x][j]]--;
      if(grad[v[x][j]]==0){
        nr++;
        s[nr]=v[x][j];
      }
    }
  }
}


int main()
{citire(n);
top();
for(int i=1;i<=n;i++)
g<<s[i]<<" ";
return 0;
    
}