Cod sursa(job #1978736)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 8 mai 2017 18:18:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define DIMN 50005
FILE *f=fopen("sortaret.in","r"), *g=fopen("sortaret.out","w");

using namespace std;

int N, M, d[DIMN], Q[DIMN];              // d = gradul interior (cate intra)
vector <int> v[DIMN];

void Citire(){

    int i, x, y;

    fscanf(f,"%d %d\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%d %d\n",&x,&y);
        v[x].push_back(y);
        d[y] ++;
    }

}

void SortareTopologica(){

    int i, k1, k2, NOD, vNOD;

    k1 = 1;
    k2 = 0;

    for(i=1;i<=N;i++)                   // Pun nodurile cu grad intern 0
        if( d[i] == 0 )
            Q[++k2] = i;

    while( k1 <= k2 ){

        NOD = Q[k1++];
        for(i=0;i<v[NOD].size();i++){
            vNOD = v[NOD][i];
            d[vNOD] --;
            if( d[vNOD] == 0 )
                Q[++k2] = vNOD;
        }

    }

    for(i=1;i<=N;i++)
        fprintf(g,"%d ",Q[i]);

}

int main(){

    Citire();
    SortareTopologica();

return 0;
}