Cod sursa(job #2571362)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 4 martie 2020 22:34:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 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 de[NMAX];
int n,m;
void citire();
priority_queue<int>H;
vector<int> sol;
int main()
{citire();
     return 0;
}
void citire()
{int i,x,y;
  fin>>n>>m;
  for(i=1;i<=m;i++)
    {
     fin>>x>>y;
     g[x].push_back(y);
     de[x]++;
     gt[y].push_back(x);
    }
  for(i=1;i<=n;i++)
        if(!de[i])
            H.push(i);
  while(!H.empty())
        {
         vector<int>act;
         while(!H.empty())
            {
             act.push_back(  H.top() );
             sol.push_back(H.top());
             H.pop();
            }
         for(i=0;i<act.size();i++)
            {int nr=act[i];
             for(int j=0;j<  gt[nr].size();j++)
                 {de[  gt[nr][j]]--;
                  if(!de[  gt[nr][j]])
                      H.push(gt[nr][j]);
                 }

            }
        }
    for(i=sol.size()-1;i>=0;i--)
            fout<<sol[i]<<" ";

}