Cod sursa(job #3124848)

Utilizator sorinturdaSorin Turda sorinturda Data 30 aprilie 2023 11:58:41
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int n, m;
    int *viz,*start,*finish;
    int **A;
    int ciclu;
    int drum_multiplu;
} Graf;

typedef struct _pair {
    int first, second;
} pair;

int t=0;

void DFS(int u, Graf *g) {
//    printf("%d ",u);
    g->start[u]=++t;
    g->viz[u]=1;
    for(int v=1; v<=g->n; v++) {
        if(g->A[u][v]==1)
            DFS(v,g);
    }
    g->finish[u]=++t;
}



int main() {
    FILE *f=fopen("sortaret.in","r");
    if(!f)
        return -1;
    Graf g;
    g.ciclu=0;
    g.drum_multiplu=0;
    fscanf(f,"%d %d",&g.n,&g.m);
    g.A=calloc(g.n+1,sizeof(int*));
    for(int i=1; i<=g.n; i++)
        g.A[i]=calloc(g.n+1,sizeof(int));
    g.viz=calloc(g.n+1,sizeof(int));
    g.start=calloc(g.n+1,sizeof(int));
    g.finish=calloc(g.n+1,sizeof(int));
    int u, v;
    while (fscanf(f,"%d %d",&u, &v)==2) {
        g.A[u][v]=1;
    }
    fclose(f);
    for(int i=1; i<=g.n; i++) {
        if(g.viz[i]==0)
            DFS(i,&g);
    }

    FILE *f2=fopen("sortaret.out","w");
    pair *ans=calloc(g.n+1,sizeof(pair));
    for(int i=1; i<=g.n; i++) {
        ans[i].first=i;
        ans[i].second=g.finish[i];
    }
    for(int i=1; i<=g.n; i++) {
        for(int j=i+1; j<=g.n; j++) {
            if(ans[i].second > ans[j].second) {
                pair aux=ans[i];
                ans[i]=ans[i];
                ans[i]=aux;
            }
        }
    }
    for(int i=1; i<=g.n; i++)
        fprintf(f2,"%d ",ans[i].first);
    fclose(f2);
    free(g.finish);
    for(int i=1; i<=g.n; i++)
        free(g.A[i]);
    free(g.A);
    free(g.viz);
    free(g.start);
    free(ans);
    return 0;
}