Cod sursa(job #1980331)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 12 mai 2017 21:08:02
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 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], gin[nmax], cap[nmax], stiva[nmax], vf, nrm=1;
int16_t viz[nmax];
///lista de adacenta
struct muchii
{
    int32_t x, y;
}muc[mmax];

int16_t found(int32_t x, int32_t y)
{
    int32_t i;
    for(i=1; i<= nrm; i++)
        if((muc[i].x==x)&&(muc[i].y==y)) return 1;
    return 0;
}
void citire()
{
    int32_t i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        if(!found(x, y))
        {
            muc[nrm].x=x;
            muc[nrm].y=y;
            nrm++;
        }
      ///elimini muchiile duble
    }

    m=nrm-1;
    for(i=1; i<=m; i++)
    {
        aux[muc[i].x]++;
        gin[muc[i].y]++;
    }

    cap[1]=1;
    for(i=2; i<=n+1; i++)
    {
        cap[i]= cap[i-1]+ aux[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 sortare2()
{
    int32_t i, j, temp;
    ///bagi in stiva nodurile cu grad interior 0
    for(i=1; i<=n; i++)
       if(!gin[i]) {vf++; stiva[vf]=i; viz[i]=1;}
    while(vf!=0)
    {
        //iei un nod din stiva, il afisezi
        //decr gin vecinilor si il elimini
        f2<<stiva[vf]<<" ";
        temp=stiva[vf];
        vf--;///necesar inainte ca sa nu analizezi de 2 ori acelasi nod

        for(j=cap[temp]; j<cap[temp+1]; j++)
           if(!viz[v[j]])
        {
            gin[v[j]]--;
            if(!gin[v[j]]) {vf++; stiva[vf]=v[j];  viz[v[j]]=1;}
        }


    }
}
int main()
{
   citire();///+lista adiacenta
   sortare2();
    return 0;
}