Cod sursa(job #3261624)

Utilizator solicasolica solica solica Data 7 decembrie 2024 09:06:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 5e4+9;

vector<int>g[NMAX];

queue<int>q;

int n,m,i,j;

int in[NMAX];

void input ();

void topsort ();

int main()
{
    input ();
    topsort();
    return 0;
}

void topsort ()
{
    for (i=1; i<=n; i++)
    {
        if (in[i]==0)
        {
            q.push (i);
        }
    }
    while (!q.empty ())
    {
        int node=q.front();
        q.pop();
        fout<<node<<' ';
        for (auto it : g[node])
        {
            in[it]--;
            if (in[it]==0)
            {
                q.push (it);
            }
        }
    }
}

void input ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        int a,b;
        fin>>a>>b;
        g[a].push_back (b);
        in[b]++;
    }
}