Cod sursa(job #1980308)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 12 mai 2017 20:25:09
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdint.h>
#include <fstream>
#include <stdlib.h>
#define nmax 50001
#define mmax 100001
using namespace std;
fstream f1("sortaret.in", ios::in);
fstream f2("sortaret.out", ios::out);
int32_t n, m, v[mmax*2], aux[nmax], cap[nmax], stiva[nmax], vf;
int16_t viz[nmax];
///lista de adacenta
struct muchii
{
    int32_t x, y;
}muc[mmax];
struct  nod
{
    nod* urm;
    int32_t info;
} l[nmax], * prim;

void citire()
{
    int32_t i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        muc[i].x=x;
        muc[i].y=y;
        aux[x]++;
    }
    cap[1]=1;
    for(i=2; i<=n; i++)
    {
        cap[i]= cap[i-1]+ aux[i-1];
        aux[i-1]=cap[i-1];
    }
    aux[i-1]=cap[i-1];

    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;
        v[aux[x]]=y;
        aux[x]++;

    }
}
void dfs(int32_t nod)
{
    int32_t i;
    viz[nod]=1;
    for(i=cap[nod]; i<cap[nod+1]; i++)
        if(!viz[v[i]])
    {
        viz[v[i]]=1;
        dfs(v[i]);
        vf++;
        stiva[vf]=v[i];///adaugi nodurile la lista in ordine inversa
    }
}
void adauga()
{
    int32_t i;
    for(i=1; i<=vf; i++)
    {
        //adaugi nodul stiva[i] in fata listei l
        nod *p= new nod;
        p->info=stiva[i];
        p->urm=prim;
        prim=p;
    }

}
void sortare()
{
    int32_t i;
    for(i=1; i<=n; i++)
        if(!viz[i])
    {
        vf=0;
        dfs(i);
        vf++;
        stiva[vf]=i;
        adauga();///adaugi el stivei in fata listei rezultat
    }
}
void afisare()
{
    nod *p;
    for(p=prim; p!=0; p=p->urm)
        f2<<p->info<<" ";
}
int main()
{
   citire();///+lista adiacenta
   sortare();
   afisare();
    return 0;
}