Cod sursa(job #2424748)

Utilizator teodor.dumitrescuDumitrescu Teodor teodor.dumitrescu Data 23 mai 2019 20:05:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

vector <int> graf[50005];
vector <int> graft[50005];
queue <int> coada;
int grad[50005];
void sortaret(int N)
{
    int i,x,lim;
    for(i=1;i<=N;i++)
        if(graft[i].empty()==1)
        {
            coada.push(i);
            //cout<<i<<" ";
        }
        //cout<<endl;
    while(coada.empty()==0)
    {
        x=coada.front();
        coada.pop();
        lim=graf[x].size();
        out<<x<<" ";
        for(i=0;i<lim;i++)
        {
            grad[graf[x][i]]--;
            if(grad[graf[x][i]]==0)
            {
                coada.push(graf[x][i]);
                //cout<<graf[x][i]<<" ";
            }
        }
    }
}
int main()
{
    int N,M,i,x,y;
    in>>N>>M;
    for(i=1;i<=M;i++)
    {
        in>>x>>y;
        graf[x].push_back(y);
        graft[y].push_back(x);
        grad[y]++;
    }
    sortaret(N);
    return 0;
}