Cod sursa(job #332745)

Utilizator levap1506Gutu Pavel levap1506 Data 19 iulie 2009 16:32:09
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>

#define maxn 100000
using namespace std;
int rN,N,M,i,j,aa,ab,c[maxn/2],sortat[maxn/2+100];
vector<int> d[maxn/2+1];
int main() {
    ifstream in;
    ofstream out;
    in.open("sortaret.in");
    out.open("sortaret.out");
    in >> N >> M;
    for (i=0;i<M;i++)
     {
         in>>aa>>ab;
         d[aa].push_back(ab);
         ++c[ab];
     }
    for (i=1;i<=N;i++)
      if (c[i]==0) sortat[++sortat[0]]=i;
    vector<int>::iterator vcounter;
    for (i=1;i<=N;i++)
     {
         int x=sortat[i];
         for (vcounter=d[x].begin(); vcounter!=d[x].end(); vcounter++)
           {
               c[*vcounter]--;
               if (c[*vcounter]==0) sortat[++sortat[0]]=*vcounter;
           }
     }
    for (i=1;i<=N;i++)
     out<<sortat[i]<<" ";
     out.close();
    return 0;
}