Cod sursa(job #168787)

Utilizator fogabFodor Gabor fogab Data 31 martie 2008 19:37:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <vector.h>

#define MAXN 50100

int n, in[MAXN],sol[MAXN],r;
vector<int> mat[MAXN];

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

int m,x,y;

fin >> n;

for (fin >> m;m;m--){
    fin >> x >> y;
    mat[x].push_back(y);
    in[y]++;
    }

for (int i=1;i<=n;i++)
  if (!in[i]) sol[r++] = i;

int i = 0;

while (i != r){
  in[sol[i]] = -1;
  fout << sol[i] << " ";
  for (vector<int>::iterator it = mat[sol[i]].begin();
     it != mat[sol[i]].end(); ++it) {
  in[*it]--;
  if (!in[*it])
    sol[r++] = *it;
  }  
  i++;      
}

fin.close();
fout.close();
    
return 0;
}