Cod sursa(job #2115549)

Utilizator RenataRenata Renata Data 26 ianuarie 2018 21:18:59
Problema Sortare topologica Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.98 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);

    int l[n+1][n+1], a, b; // risipa de memorie

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

    for(i=1;i<n+1;i++)
        l[i][0]=1;

    for(i=0; i<m; i++)
       {
            fscanf(f, "%d %d", &a, &b);
            l[a][l[a][0]++] =b;
       }

    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)
            {

                if(graf[stiva[st]].stare == nevizitat)
                {
                    graf[stiva[st]].stare = vizitat;
                    graf[stiva[st]].descoperit = timp++;
                    graf[stiva[st]].parinte = 0;

                }

                ok=0;
                for(j=1; j<l[stiva[st]][0]; j++)
                    if(graf[l[stiva[st]][j]].stare == nevizitat )
                    {
                        a = l[stiva[st]][j];
                        stiva[++st] = a;
                        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=index-1;i>=0;i--)
        fprintf(g, "%d ", rez[i]);


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