Cod sursa(job #2325102)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 21 ianuarie 2019 22:32:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>
#include <queue>
#define LMAX 500005
#define pb push_back

using namespace std;
FILE *fin=fopen("sortaret.in","r");
FILE *fout=fopen("sortaret.out","w");

vector<int>G[LMAX];
int deg[LMAX];
queue<int>q;
int x, y;
int n, m;

int main()
{
    fscanf(fin,"%d %d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        fscanf(fin,"%d %d",&x,&y);
        G[x].pb(y);
        ++deg[y];
    }
    for (int i=1;i<=n;++i)
    {
        if (!deg[i])
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int act = q.front();
        fprintf(fout,"%d ",act);
        q.pop();
        for (int i=0;i<G[act].size();++i)
        {
            --deg[G[act][i]];
            if (!deg[G[act][i]])
            {
                q.push(G[act][i]);
            }
        }
    }
    fprintf(fout,"\n");
    fclose(fin);
    fclose(fout);
    return 0;
}