Cod sursa(job #2654784)

Utilizator marinaoprOprea Marina marinaopr Data 2 octombrie 2020 11:55:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <vector>
#include <queue>

#define NMAX 50005

using namespace std;

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

vector <int> graf[NMAX];
queue <int> liber;
int n,m,i,fr[NMAX],x,y;

int main()
{
    fscanf(fin, "%d%d", &n,&m);

    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d%d", &x,&y);
        graf[x].push_back(y);
        fr[y]++;
    }

    for(i=1; i<=n; ++i)
        if(!fr[i])
            liber.push(i);

    while(!liber.empty())
    {
        x = liber.front();

        for(i=0; i<graf[x].size(); ++i)
        {
            fr[graf[x][i]] --;
            if(!fr[graf[x][i]])
                liber.push(graf[x][i]);
        }

        fprintf(fout, "%d ", x);
        liber.pop();
    }

    fclose(fin);
    fclose(fout);
    return 0;
}