Cod sursa(job #2991090)

Utilizator Pasca__GabrielPasca Gabriel Pasca__Gabriel Data 9 martie 2023 08:48:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define MAXN 50100
#define pb push_back

int n,m,deg[MAXN],q[MAXN];
vector<int> g[MAXN];

void citire()
{
    int i,a,b;
    f>>n>>m;
    for(i=1;i<=m;i++)
        {
            f>>a>>b;
            g[a].pb(b);
            deg[b]++;
        }
}

void solve()
{
    int i,x;
    vector<int>::iterator it;
    for(x=1;x<=n;x++)
        if(deg[x]==0) q[++q[0]]=x;
    for(i=1;i<=n;i++)
    {
        x=q[i];
        for(it=g[x].begin();it!=g[x].end();it++)
            {
                deg[*it]--;
                if(deg[*it]==0) q[++q[0]]=*it;
            }
    }
}

void afisare()
{
    for(int i=1;i<=n;i++)
        k<<q[i]<<" ";
}

int main()
{
    citire();
    solve();
    afisare();
    return 0;
}