Cod sursa(job #1926321)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 14 martie 2017 11:37:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <vector>
#include <queue>
#define LMAX 50002

using namespace std;
FILE *fin=fopen("sortaret.in","r");
FILE *fout=fopen("sortaret.out","w");

vector<int> G[LMAX];
queue<int> Q;

int n;
int d[LMAX];

void citire();
void sortaret();

int main()
{
citire();
sortaret();
fclose(fin);
fclose(fout);
return 0;
}

void citire()
    {
     int i;
     int m;
     int x, y;
     fscanf(fin,"%d %d",&n,&m);
     for (i=1;i<=m;i++)
         {
          fscanf(fin,"%d %d",&x, &y);
          d[y]++;
          G[x].push_back(y);
         }
    }

void sortaret()
    {
     int i;
     int x;
     for (i=1;i<=n;i++)
          if (!d[i])
              Q.push(i);
     while (!Q.empty())
           {
            x=Q.front();
            Q.pop();
            fprintf(fout,"%d ",x);
            for (i=0;i<G[x].size();i++)
                 if (d[G[x][i]]>0)
                     {
                      d[G[x][i]]--;
                      if (!d[G[x][i]])
                          Q.push(G[x][i]);
                     }
           }
     fprintf(fout,"\n");
    }