Cod sursa(job #2526130)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 18 ianuarie 2020 12:03:30
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <cstdio>
using namespace std;
FILE *fin, *fout;
const int nmax = 50001;
const int mmax = 100001;
int lst[nmax],vf[mmax],urm[mmax],nr,n;
int nrp[nmax],q[nmax];

void adauga(int x, int y){
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
    nrp[y]++;
}

void sortare_topologica(){
    int st,dr,x;
    st = 0, dr = -1;
    for(int i=1; i<=n; i++)
        if(nrp[i] == 0)
            q[++dr] = i;
    while(st <= dr){
        x = q[st++];
        fprintf(fout,"%d ",x);
        for(int p=lst[x]; p != 0; p=urm[p]){
            int next = vf[p];
            nrp[next]--;
            if(nrp[next] == 0)
                q[++dr] = next;
        }
    }
}

int main()
{
    int m,i,x,y;
    fin = fopen("sortaret.in","r");
    fout = fopen("sortaret.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=0; i<m; i++){
        fscanf(fin,"%d %d",&x,&y);
        adauga(x,y);
    }
    sortare_topologica();
    fclose(fin);
    fclose(fout);
    return 0;
}