Cod sursa(job #1654934)

Utilizator andrei_bB. Andrei andrei_b Data 17 martie 2016 16:47:18
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;

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

const int Nmax=50005;
const int Mmax=100005;

int n,m,a,b,nr,cate,u,primul;
int lst[Nmax],vf[Mmax],urm[Nmax],ordine[Nmax],q[Nmax];

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

void bfs ( int x ){

    int p=0,poz,y;

    while ( p < u ){
        x=q[p++];
        poz=lst[x];
        fout<<x<<' ';
        while ( poz != 0 ){
            y=vf[poz];
            poz=urm[poz];
            ordine[y]--;
            if ( ordine[y] == 0 ){
                q[u++]=y;
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for ( int i=1 ; i<=m ; i++ ){
        fin>>a>>b;
        adauga(a,b);
    }
    for ( int i=1 ; i<=n ; i++ ){
        if ( ordine[i] == 0 ){
            q[u++]=i;
            if ( u == 0 )
                primul=i;
        }
    }
    bfs(primul);
}