Cod sursa(job #1452640)

Utilizator Emil64Emil Centiu Emil64 Data 21 iunie 2015 15:47:02
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

struct _nod
{
    int tata, timp, index, nc;
};

_nod nod[50001]= {0};

bool cmp(_nod nod1, _nod nod2)
{
    return (nod1.timp<nod2.timp);
}

void tipar(int poz)
{

    int i;
    cout<<nod[poz].index<<" ";
    if(nod[poz].nc)
    {
        int pz=poz+1, index=nod[poz].index, nc=nod[poz].nc;
        while(nod[pz].tata!=index)
            pz++;
        for(i=1; i<=nc; i++)
            tipar(pz+i-1);
    }
}

int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int i, j, n, m, a, b;
    //_nod nod[50001]={0};
    f>>n>>m;
    for(i=1; i<=m; i++)
    {

        f>>a>>b;
        nod[b].tata=a;
        nod[b].timp=nod[a].timp+1;
        nod[a].nc++;
    }
    for(i=1; i<=n; i++)
        nod[i].index=i;
    sort(nod+1, nod+1+n, cmp);
    int nc=0;
    while(nod[nc+1].tata==0)
        nc++;
    for(i=1;i<=nc;i++)
        tipar(i);
}