Cod sursa(job #1572738)

Utilizator dinu_sergiuDinu Sergiu Andrei dinu_sergiu Data 19 ianuarie 2016 08:38:43
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>

using namespace std;

FILE *f=fopen("sortaret.in", "r");
FILE *g=fopen("sortaret.out", "w");

struct nod
{
    int info;
    nod *urm;
} *prim[50001];

void Addnod(int x, int y)
{
    nod *p=new nod;
    p->info=y;
    p->urm=prim[x];
    prim[x]=p;
}

int n, m, grad[50001], rad, c[50001];

void Citire()
{
    int i, x, y;
    fscanf(f, "%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        fscanf(f, "%d%d", &x, &y);
        Addnod(x, y);
        grad[y]++;
    }

}

void Calc1()
{
    int i;
    for(i=1; i<=n; i++)
        if(grad[i]==0)
    {
        rad=i;
        break;
    }
}

void BFS()
{
    int pr, ul, i, x;
    nod *p;
    pr=ul=1;
    c[1]=rad;
    while(pr<=ul)
    {
        x=c[pr];
        pr++;
        for(p=prim[x]; p!=NULL; p=p->urm)
        {
            ul++;
            c[ul]=p->info;

        }
    }
}

void Afisare()
{
    int i;
    for(i=1; i<=n; i++)
        { fprintf(g, "%d ", c[i]);
        }
}


int main()
{
    Citire();
    Calc1();
    BFS();
    Afisare();
    fclose(f);
    fclose(g);
    return 0;
}