Cod sursa(job #2104853)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 12 ianuarie 2018 12:50:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int>L[50005];
queue <int>q;
int viz[50005], grad[50005], n, m;
void Citire()
{
    int x, y;

    fin >> n >> m;
    while(fin >> x >> y)
        L[x].push_back(y),
        grad[y]++;
}
void Sortare()
{
    int el;

    for(int i = 1; i <= n; i++)
        if(grad[i] == 0)
            q.push(i);

    while(!q.empty())
    {
        el = q.front();
        viz[el] = 1;
        q.pop();

        fout << el << " ";

        for(auto i : L[el])
        {
            grad[i]--;
            if(grad[i] == 0 && !viz[i])
                q.push(i);
        }
    }
}
int main()
{
    Citire();
    Sortare();
    return 0;
}