Pagini recente » Cod sursa (job #161290) | Cod sursa (job #192439) | Cod sursa (job #2752488) | Cod sursa (job #2214713) | Cod sursa (job #3124848)
#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;
}