Cod sursa(job #2637195)

Utilizator numecompletnume complet numecomplet Data 21 iulie 2020 18:57:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
#define NMAX 50009
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<int> g[NMAX];
vector<int> gt[NMAX];
int d[NMAX];
int n,m,i;
queue <int> Q;
vector<int> sol;
void citire();
int main()
{citire();
 for(i=1;i<=n;i++)
    if( !d[i])
       Q.push(i);
 while(!Q.empty())
    {
     int x=Q.front();Q.pop();
     for(i=0;i< gt[x].size();i++)
        {int vec=gt[x][i];
         d[vec]--;
         if(d[vec]==0)
                Q.push(vec);
        }
     sol.push_back(x);
    }
    for(i=sol.size()-1;i>=0;i--)
         fout<<sol[i]<<" ";
    return 0;
}
void citire()
{
  int i;
  int x,y;
  fin>>n>>m;
  for(i=1;i<=m;i++)
    {
     fin>>x>>y;
     g[x].push_back(y);

     gt[y].push_back(x);

     d[x]++;
    }
}