Cod sursa(job #1114546)

Utilizator tannous.marcTannous Marc tannous.marc Data 21 februarie 2014 19:00:17
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
using namespace std;
int succ[49901][100],pred[50001],q[50001];
int main()
{
  ifstream in("sortaret.in");
  ofstream out("sortaret.out");
  int n,r,a,b;
  int i,j;
    in>>n;
    in>>r;
      for(i=1;i<=r;i++)
      {
        in>>a>>b;
          pred[b]++;
          succ[a][0]++;
          succ[a][succ[a][0]]=b;
      }
      int p=1;
      int u=0;
      for(i=1;i<=n;i++)
        if(pred[i]==0) q[++u]=i;
      while(p<=u)
        {
          int t=q[p];
            for(i=1;i<=succ[t][0];i++)
            {
              pred[succ[t][i]]--;
                if(pred[succ[t][i]]==0) q[++u]=succ[t][i];
            }
                p++;
        }
      if(u==n)
            for(j=1;j<=u;j++)
              out<<q[j]<<" ";
      else out<<"-1";
  return 0;
}