Cod sursa(job #2357753)

Utilizator ptr22222Petru Popescu ptr22222 Data 27 februarie 2019 18:21:56
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int N=1000002;
int nrp[N],n,m,xs;
queue <int> q;
vector <int> a[N];

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

void bfs()
{
    //memset(d,-1,sizeof(d));
    for(int i=1;i<=n;i++)
    {
        if(nrp[i]==0)
        {
           q.push(i);
        }
    }
    while(!q.empty())
    {
       int x=q.front();
       q.pop();
       out<<x<<' ';
       for(auto y:a[x])
       {
           nrp[y]--;
           if(nrp[y]==0)
           {
              q.push(y);
           }
       }
    }
}

int main()
{
    citire();
    bfs();
    return 0;
}