Cod sursa(job #453816)

Utilizator sapiensCernov Vladimir sapiens Data 11 mai 2010 13:31:07
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <list>
using namespace std;

ifstream fin; ofstream fout;
list <long> a[50000],b[50000],c,d;
list <long>::iterator it;
long n,m,i,x,y,k;

void remove (long x,long y) {
     list <long>::iterator ot;
     for (ot=b[x].begin (); *ot!=y; ot++);
     b[x].erase (ot);
}

int main () {
    fin.open ("sortaret.in"); fout.open ("sortaret.out");
    fin>>n>>m;
    for (i=0; i<m; i++) {
        fin>>x>>y;
        a[x].push_back (y);
        b[y].push_back (x);
    }
    for (i=1; i<=n; i++) {
        a[i].sort (); b[i].sort ();
        a[i].unique (); b[i].unique ();
    }
    for (i=1; i<=n; i++) if (b[i].empty ()) c.push_back (i);
    while (!c.empty ()) {
          k=c.front ();
          c.pop_front ();
          d.push_back (k);
          for (it=a[k].begin (); it!=a[k].end (); it++) {
//              b[*it].remove (k);
              remove (*it,k);
              if (b[*it].empty ()) c.push_back (*it);
          }
    }
    for (it=d.begin (); it!=d.end (); it++) fout<<*it<<" ";
    fout<<endl;
    fin.close (); fout.close ();
    return 0;
}