Cod sursa(job #1603792)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 17 februarie 2016 19:28:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>

const int nmax=50001;

struct element
{
    int nod,next;
};

int head[nmax];
int ans[nmax];
bool viz[nmax];
int pos;

element buff[2*nmax];

void push(int n1, int n2, int pos)
{
    buff[pos].nod=n2;
    buff[pos].next=head[n1];
    head[n1]=pos;
}

void dfs (int nod)
{
    int i;

    viz[nod]=true;
    i=head[nod];
    while (i)
    {
        if (! viz[buff[i].nod])
            dfs(buff[i].nod);
        i=buff[i].next;
    }
    pos++;
    ans[pos]=nod;
}

int main()
{
    int i,n,m,x,y;
    FILE *f;

    f=fopen("sortaret.in","r");
    fscanf(f,"%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        fscanf(f,"%d%d",&x,&y);
        pos++;
        push(x,y,pos);
    }
    pos=0;


    /*for (i=1; i<=n; i++)
    {
        printf("%d :",i);
        int j=head[i];
        while (j)
        {
            printf("%d ",buff[j].nod);
            j=buff[j].next;
        }
        printf("\n");
    }*/

    for (i=1; i<=n; i++)
    {
        if (!viz[i])
            dfs(i);
    }

    f=fopen("sortaret.out","w");
    for (i=pos; i>=1; i--)
        fprintf(f,"%d ",ans[i]);
    fclose(f);
}