Cod sursa(job #653396)

Utilizator galbenugalbenu dorin galbenu Data 27 decembrie 2011 21:08:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<iostream>
#include<fstream>
#include<ctime>
#include<cctype>
#define lmax 50000
#define mmax 100000
using namespace std;
ifstream f("sortaret.in",fstream::in);
ofstream g("sortaret.out",fstream::out);
typedef struct
{
    short int x,y;
}muchie;
muchie M[mmax];
short int q[lmax],GE[lmax],GI[lmax],viz[lmax],contviz;
short int n,m,i,cq;
void citire()
{
    short int x,y,i;
    f>>n>>m;
    for(i=1;i<=m;i++)
     {f>>M[i].x>>M[i].y;
      GE[M[i].x]+=1;
      GI[M[i].y]+=1;
     }
}
void rezolv()
{ short int i,j;
    while(contviz<n)
{
     for(i=1;i<=n;i++)
      if(GI[i]==0 && viz[i]==0)
       {
           viz[i]=1;
           contviz+=1;
           q[++cq]=i;
       }
    for(i=1;i<=cq;i++)
     for(j=1;j<=m;j++)
      if(M[j].x==q[i] && viz[M[j].y]==0)
       GI[M[j].y]--;}
}
int main()
{
    citire();
    rezolv();
       for(i=1;i<=n;i++)
    g<<q[i]<<" ";
    f.close();
    g.close();
    return 0;
}