Cod sursa(job #2130056)

Utilizator mariarinzilaMaria Brinzila mariarinzila Data 13 februarie 2018 13:33:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#define NMAX 50005

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int nr, n, m;
vector <int> G[NMAX];
vector <int> niv(NMAX);
vector <int> gi(NMAX);

void citire();
void sortare();

int main()
{citire();
 sortare();
 return 0;
 fin.close();
 fout.close();
}

void citire()
    {int i, x, y;
     fin>>n>>m;
     for (i=1; i<=m; i++)
          {fin>>x>>y;
           G[x].push_back(y);
           gi[y]++;
          }
    }


void sortare()
    {int i, j, lg;
     while (nr<n)
            {lg=0;
             for (i=1; i<=n; i++)
                  if (gi[i]==0)
                      niv[++lg]=i;
             for (i=1; i<=lg; i++)
                  {fout<<niv[i]<<' ';
                   gi[niv[i]]=-1; nr++;
                   for (j=0; j<G[niv[i]].size(); j++)
                        gi[G[niv[i]][j]]--;
                  }
            }
    }