Cod sursa(job #1129147)

Utilizator dascalutudorDascalu Tudor dascalutudor Data 27 februarie 2014 20:24:36
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
const int Nmax=5000;
int mat[Nmax][Nmax],v[Nmax],coada[Nmax],noduri[Nmax],t[Nmax],n,m;
void bfs(int ns)
{   int ps=1,pf=1,i;
    coada[ps]=ns;
    v[ns]=1;
    if(noduri[ns]==0) out<<ns<<" ";
    while(ps<=pf)
    {   for(i=1;i<=n;i++)
        {   if(v[i]==0)
            if(mat[coada[ps]][i]==1)
            {   v[i]=1;
                pf++;
                coada[pf]=i;
                t[i]=coada[ps];
                noduri[i]--;
                if(noduri[i]==0) out<<i<<" ";
            }
        }
        ps++;
    }

}
int main()
{   int i,a,b;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {   in>>a>>b;
        mat[a][b]=1;
        noduri[b]++;
    }
    bfs(1);

    return 0;
}