Cod sursa(job #2115509)

Utilizator RenataRenata Renata Data 26 ianuarie 2018 20:38:28
Problema Sortare topologica Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 2.1 kb
#include <stdio.h>
#include <stdlib.h>
#define nevizitat 0
#define vizitat 1
#define terminat 2
struct nod
{
    int descoperit;
    int finalizat;
    int parinte;
    int stare;
};

struct muchie
{
    int n1;
    int n2;
};



int main()
{
    int n,m;
    FILE *f = fopen("sortaret.in", "r");
    FILE *g = fopen("sortaret.out", "w");
    fscanf(f, "%d %d", &n, &m);

    struct muchie l[m];
    struct nod graf[n];
    int i, j, timp=1, stiva[n], rez[n], st =0, ok=0, index=0;

    for(i=0; i<m; i++)
        fscanf(f, "%d %d", &l[i].n1, &l[i].n2);

    for(i=1; i<=n; i++)
        graf[i].stare = nevizitat;

    for(i=1; i<=n; i++)
    {
        if(graf[i].stare == nevizitat)
        {
            stiva[++st] = i;
            while (st>0)
            {
                //printf("st=%d i=%d timp=%d\n", st, i,timp );
                if(graf[stiva[st]].stare == nevizitat)
                {
                    graf[stiva[st]].stare = vizitat;
                    graf[stiva[st]].descoperit = timp++;
                    graf[stiva[st]].parinte = 0;
                    //printf("%d ", stiva[st]);
                }

                ok=0;
                for(j=0; j<m;j++)
                    if(l[j].n1 == stiva[st] && graf[l[j].n2].stare == nevizitat )
                    {
                        stiva[++st] = l[j].n2;
                        ok=1;
                        break;
                    }

                if(ok==0)
                {
                    graf[stiva[st]].stare = terminat;
                    graf[stiva[st]].finalizat = timp++;
                    rez[index++] = stiva[st];
                    if(st > 1)
                        graf[stiva[st]].parinte = stiva[st];

                    st--;

                }
            }
        }


    }

    //for(i=1; i<=n; i++)
    //{
    //    printf("i=%d %d/%d\n", i, graf[i].descoperit, graf[i].finalizat);
    //}
    //printf("Sortarea topologica: ");
    for(i=index-1;i>=0;i--)
        fprintf(g, "%d ", rez[i]);


    fclose(f);
    fclose(g);
    return 0;
}