Cod sursa(job #2580565)

Utilizator Andr31R0BAndreiRob Andr31R0B Data 13 martie 2020 19:07:26
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define pb push_back

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

const int dim = (int)(50100);

int n, m, a, b, viz[dim], deg[dim];
vector<int> G[dim];

void solve()
{
    int i, j, k;

    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
         if(!viz[j] && deg[j] == 0)
         {
            viz[j] = 1;
            out<<j<<' ';
            for(k = 0; k < G[j].size(); k++)
                deg[ G[j][k] ]--;
            break ;
         }
    }
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        G[a].pb(b), deg[b]++;
    }
    solve();

    in.close();
    out.close();
    return 0;
}